#include <bits/stdc++.h>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
const long long rest=666013;
long long t,n;
long long matrix[3][3],ans[3],aux[3],next[3][3];
int main()
{
    fin>>t;
    while(t--)
    {
        matrix[0][0]=0;
        matrix[0][1]=0;
        matrix[1][0]=1;
        matrix[1][1]=0;
        matrix[2][0]=0;
        matrix[2][1]=1;
        fin>>ans[0]>>ans[1]>>ans[2];
        fin>>matrix[2][2]>>matrix[1][2]>>matrix[0][2];
        fin>>n;
        n-=2;
        long long j=0;
        while((1LL<<j)<=n)
        {
            if((1LL<<j)&n)
            {
                for(int i=0;i<3;i++)
                    aux[i]=(ans[0]*matrix[0][i]+ans[1]*matrix[1][i]+ans[2]*matrix[2][i])%rest;
                for(int i=0;i<3;i++)
                    ans[i]=aux[i];
            }
            for(int i=0;i<3;i++)
                for(int i2=0;i2<3;i2++)
                    next[i][i2]=(matrix[i][0]*matrix[0][i2]+matrix[i][1]*matrix[1][i2]+matrix[i][2]*matrix[2][i2])%rest;
            for(int i=0;i<3;i++)
                for(int i2=0;i2<3;i2++)
                    matrix[i][i2]=next[i][i2];
            j++;
        }
        fout<<ans[2]<<"\n";
    }
    return 0;
}