#include <iostream>
#include <fstream>

using namespace std;

#define MOD 666013

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

long long m[3][3], z[3][3], q[3][3];

int main() {
    long long x,y,zc,a,b,c,n,p,i,j,k,r;
    int t;
    fin>>t;
    while (t--){
        fin>>x>>y>>zc>>a>>b>>c>>n;
        m[0][0]=x;
        m[0][1]=y;
        m[0][2]=zc;
        for(i=1;i<3;i++)
            for(j=0;j<3;j++)
                m[i][j]=0;
        z[0][0] = 0;
        z[0][1] = 0;
        z[0][2] = c;
        z[1][0] = 1;
        z[1][1] = 0;
        z[1][2] = b;
        z[2][0] = 0;
        z[2][1] = 1;
        z[2][2] = a;
        p = n - 2;
        while (p){
            if (p%2==1){
                for(i=0;i<3;i++)
                    for(j=0;j<3;j++)
                        q[i][j]=0;
                for(j=0;j<3;j++)
                    for(k=0;k<3;k++)
                        q[0][j] = (q[0][j]+m[0][k]*z[k][j]) % MOD;

                m[0][0] = q[0][0];
                m[0][1] = q[0][1];
                m[0][2] = q[0][2];
            }
            for(i=0;i<3;i++)
                for(j=0;j<3;j++)
                    q[i][j] = 0;
            for(i=0;i<3;i++)
                for(j=0;j<3;j++)
                    for(k=0;k<3;k++)
                        q[i][j] = (q[i][j] + z[i][k] * z[k][j]) % MOD;
            for(i=0;i<3;i++)
                for(j=0;j<3;j++)
                    z[i][j] = q[i][j];
            p /= 2;
        }
        r=m[0][2]%MOD;
        if (r<0)
           r+=MOD;
        fout<<r<<'\n';
    }
    return 0;
}