#include <fstream>
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
const int R = 666013;
int x, y, z, a, b, c, n;
long long inm[4][4], rez[4][4], aux[4][4], ms[4][4];
void init(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            inm[i][j] = rez[i][j] = 0;
    for(int i=1;i<=3;i++)
        rez[i][i] = 1;
    inm[1][3] = c;
    inm[2][3] = b;
    inm[3][3] = a;
    inm[2][1] = inm[3][2] = 1;
    ms[1][1] = x;
    ms[1][2] = y;
    ms[1][3] = z;
}
void multiplyMatrix(long long mat[][4], long long im[][4]){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            aux[i][j] = 0;
            for(int p=1;p<=3;p++)
                aux[i][j] = (aux[i][j] + 1LL * mat[i][p] * im[p][j]) % R;
        }
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            mat[i][j] = aux[i][j];
}
void fastExpMatrix(int n){
    init();
    for(;n>0;n>>=1){
        if(n%2)
            multiplyMatrix(rez,inm);
        multiplyMatrix(inm,inm);
    }
}
int main()
{
    int T;
    in>>T;
    for(int q=1;q<=T;q++){
        in>>x>>y>>z>>a>>b>>c>>n;
        fastExpMatrix(n-2);
        multiplyMatrix(ms,rez);
        out<<ms[1][3]<<"\n";
    }
    in.close();
    out.close();
    return 0;
}