#include<stdio.h>
int m;
int bi[100];
int x;
int a[4][4];
int apow[4][4];
int i;
int y;
int z;
int t;
int k;
int l;
int n;
# define mod 666013
int prod(int caz)
{
    int prod[4][4] = {0};
    if (caz == 1)
      {
          for(int i = 1; i <= 3; i++)
           for(int j = 1; j <= 3; j++)
            for(int k = 1; k <= 3; k++)
             prod[i][j] = (prod[i][j] + (apow[i][k] * apow[k][j]) % mod) % mod;
          for(int i = 1; i <= 3; i++)
           for(int j = 1; j <= 3; j++)
            apow[i][j] = prod[i][j];
      }
    if (caz == 2)
      {
          for(int i = 1; i <= 3; i++)
           for(int j = 1; j <= 3; j++)
            for(int k = 1; k <= 3; k++)
             prod[i][j] = (prod[i][j] + (apow[i][k] * a[k][j]) % mod) % mod;
          for(int i = 1; i <= 3; i++)
           for(int j = 1; j <= 3; j++)
            apow[i][j] = prod[i][j];
      }

    return 0;
}
void init()
{
    for(int i = 1; i <= 3; i++)
     for(int j = 1; j <= 3; j++)
      apow[i][j] = (i == j);
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    a[1][2] = 1;
    a[2][3] = 1;
    for(; t; t--)
     {
       scanf("%d %d %d %d %d %d %d",&x, &y, &z, &k, &l, &m, &n);
       init();
       a[3][1] = m % mod;
       a[3][2] = l % mod;
       a[3][3] = k % mod;
       for(i = 1; n ; n /= 2)
        bi[i++] = n % 2;
       for(int j = i - 1; j > 0; j--)
        {
            prod(1);
            if (bi[j]) prod(2);
        }
       int sum = 0;
       sum = ((apow[1][1] * x) % mod + (apow[1][2] * y) % mod + (apow[1][3] * z) % mod) % mod;
       printf("%d \n", sum);

     }

    return 0;
}