#include<stdio.h>
long long m;
long long bi[100];
long long x;
long long a[4][4];
long long apow[4][4];
long long i;
long long y;
long long z;
long long t;
long long k;
long long l;
long long n;
# define mod 666013
int prod(long long caz)
{
    long long 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("%lld",&t);
    a[1][2] = 1;
    a[2][3] = 1;
    for(; t; t--)
     {
       scanf("%lld %lld %lld %lld %lld %lld %lld",&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(long long j = i - 1; j > 0; j--)
        {
            prod(1);
            if (bi[j]) prod(2);
        }
       long long sum = 0;
       sum = ((apow[1][1] * x) % mod + (apow[1][2] * y) % mod + (apow[1][3] * z) % mod) % mod;
       printf("%lld \n", sum);

     }

    return 0;
}