#include<bits/stdc++.h>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
struct matrice
{
    long long a[4][4];
};
matrice mat[31],m;
const long long K=666013;
void afis(matrice m)
{
    for(long long i=1; i<=3; i++)
    {
        for(long long j=1; j<=3; j++)
        {
            cout<<m.a[i][j]<<" ";
        }
        cout<<endl;
    }
}
matrice mult(matrice a,matrice b)
{
    matrice c;
    for(long long i=1; i<=3; i++)
        for(long long j=1; j<=3; j++)
        {
            c.a[i][j]=0;
            for(long long ii=1; ii<=3; ii++)
            {
                c.a[i][j]+=(a.a[i][ii]*b.a[ii][j])%K;
                c.a[i][j]%=K;
            }
            c.a[i][j]%=K;
        }
    return c;
}
int main()
{
    int t;
    fin>>t;
    while(t--)
    {
        long long x,y,z,n;
        fin>>x>>y>>z>>mat[0].a[3][3]>>mat[0].a[2][3]>>mat[0].a[1][3]>>n;
        n-=2;
        mat[0].a[2][1]=mat[0].a[3][2]=1;
        for(long long i=1; i<=31; i++)
            mat[i]=mult(mat[i-1],mat[i-1]);
        for(long long i=1; i<=3; i++)
            for(long long j=1; j<=3; j++)
                m.a[i][j]=0;
        for(long long i=1; i<=3; i++)
            m.a[i][i]=1;
        for(long long nr=0; nr<=30; nr++)
        {
            if(((1<<nr)&n)!=0)
            {
                m=mult(m,mat[nr]);
            }
        }
        fout<<x*m.a[1][3]+y*m.a[2][3]+z*m.a[3][3]<<"\n";
    }


}