#include<bits/stdc++.h>
using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

const long long r=666013;

void putM(long long v[3][3],long long w[3][3]){
    long long a[3][3];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            a[i][j]=(v[i][0]*w[0][j])%r+(v[i][1]*w[1][j])%r+(v[i][2]*w[2][j])%r;

    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            v[i][j]=a[i][j]%r;
}

void lgput(long long v[3][3],int p){


    if(p!=1){
    long long a[3][3];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            a[i][j]=v[i][j];
    putM(v,v);
    if(p%2==0) lgput(v,p/2); //daca puterea e para
    else{
        lgput(v,(p-1)/2); // daca puterea este impara
        putM(v,a);
    }
    }

}

long long iepuri(){
    long long x,y,z,a,b,c;
    int n;
    f>>x>>y>>z>>a>>b>>c>>n;
    long long v[3][3]={a, b, c, 1, 0, 0, 0, 1, 0};
    long long k[3][3]={z, 0, 0, y, 0, 0, x, 0, 0};
    lgput(v,n-2);
    putM(v,k);

    return v[0][0];
}
int main(){
    int t;f>>t;
    for(int i=1;i<=t;i++)
        g<<iepuri()<<'\n';
}