#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const long long int mod = 666013;

long long int x,y,z,a,b,c,n,p;

void solve(long long int,long long int,long long int,long long int,long long int,long long int,long long int);

int main()
{
    fin>>p;
    for(;p!=0;p--)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        solve(x,y,z,a,b,c,n);
    }



}

void solve(long long int x,long long int y,long long int z,long long int a,long long int b,long long int c,long long int n)
{
    for(n-=2;n!=0;n--)
    {
        long long int aux=z;
        z=((((((a%mod)*(z%mod))%mod)+(((b%mod)*(y%mod))%mod))%mod)+((c%mod)*(x%mod)%mod)%mod);
        x=y;
        y=aux;
    }
    fout<<z<<'\n';
}