#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
long long x,y,z,a,b,c,n,t;
struct mat
{
    long long _[3][3];
};
mat mult(mat q, mat q1)
{
    mat rez;
    for(int i=0;i<=2;i++)
    {
        for(int j=0;j<=2;j++)
        {
            rez._[i][j]=0;
            for(int k=0;k<=2;k++)
            {
                rez._[i][j]=(1LL*(rez._[i][j]+(1LL*q._[i][k]*q1._[k][j])%mod))%mod;
            }
        }
    }
    return rez;
}
int exp(int s)
{
    mat a1={0,1,0,0,0,1,c,b,a};
    mat rez={1,0,0,0,1,0,0,0,1};
    for(int i=1;i<(1<<30);i=i*2)
    {
        if(s&i)
        {
            rez=mult(rez,a1);
        }
        a1=mult(a1,a1);
    }
    long long sum=(1LL*c*(rez._[0][0]*x+rez._[0][1]*y+rez._[0][2]*z))%mod;
    sum=(1LL*(sum+1LL*b*(rez._[1][0]*x+rez._[1][1]*y+rez._[1][2]*z)))%mod;
    sum=(1LL*(sum+1LL*a*(rez._[2][0]*x+rez._[2][1]*y+rez._[2][2]*z)))%mod;
    return sum;
}
int main()
{
    in>>t;
    for(int i=1;i<=t;i++)
    {
        in>>x>>y>>z>>a>>b>>c>>n;
        if(n==1)out<<y;
        else if(n==2)out<<z;
        else if(n==3)out<<(1LL*(x*c+y*b+z*a))%mod;
        else
        {
            out<<exp(n-3);
        }
        out<<'\n';
    }
    return 0;
}