#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];
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][1] = a;
    inm[1][2] = b;
    inm[1][3] = c;
    inm[2][1] = inm[3][2] = 1;
}
void multiplyMatrix(long long mat[][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] * inm[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);
        multiplyMatrix(inm);
    }
}
int main()
{
    int T,r;
    in>>T;
    for(int q=1;q<=T;q++){
        in>>x>>y>>z>>a>>b>>c>>n;
        fastExpMatrix(n-2);
        r = rez[1][1] * z + rez[1][2] * y + rez[1][3] * x;
        out<<r<<"\n";
    }
    in.close();
    out.close();
    return 0;
}