#include <fstream>
#include <cstring>
#define int64 long long
#define mod 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
int t[4][4],sol[4][4];
int64 n,a,b,c;
void mult(int a[4][4],int b[4][4],int c[4][4])
{
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3;k++)
        c[i][j]=(c[i][j]+a[i][k]*1LL*b[k][j])%mod;
}
int logpow(int64 p)
{
    int aux[4][4];
    while(p>0)
    {
        if(p%2)
        {
            memset(aux,0,sizeof(aux));
            mult(sol,t,aux);
            memcpy(sol,aux,sizeof(aux));
            p--;
        }
        memset(aux,0,sizeof(aux));
        mult(t,t,aux);
        memcpy(t,aux,sizeof(aux));
        p/=2;
    }
    return sol[1][3]%mod;
}
int main()
{
    int q;
    for(in>>q;q;q--)
    {
        memset(sol,0,sizeof(sol));
        memset(t,0,sizeof(t));
        in>>sol[1][1]>>sol[1][2]>>sol[1][3]>>t[3][3]>>t[2][3]>>t[1][3]>>n;
        if(n<=3)
        {
            if(n==0)out<<sol[1][1]<<'\n';
            if(n==1)out<<sol[1][2]<<'\n';
            if(n==2)out<<sol[1][3]<<'\n';
            continue;
        }
        t[2][1]=t[3][2]=1;
        out<<logpow(n-2)<<'\n';
    }
    return 0;
}