#include <iostream>
#include <fstream>
#define MOD 666301
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long mat[3][3], MAT[3][3],input[105][10],A,B,C,X,Y,Z,N;
int i,j,T,k;

void inm(long long a[3][3], long long b[3][3],long long c[3][3])
{
    long long d[3][3];
    int i,j,k;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
    {
        d[i][j]=0;
        for(k=0;k<3;++k)
            {d[i][j]+=a[i][k]*b[k][j]%MOD;d[i][j]%=MOD;}
    }
       for(i=0;i<3;++i)
        for(j=0;j<3;++j)c[i][j]=d[i][j];

}


void alan(long long a[3][3],long long n,long long b[3][3])
{
    if(n==0)
    {
        b[0][0]=b[1][1]=b[2][2]=1;
        b[0][1]=b[0][2]=b[1][0]=b[1][2]=b[2][0]=b[2][1]=0;
    }
    else
        {
            long long aux[3][3];
            alan(a,n/2,aux);
            inm(aux,aux,b);
            if(n%2)inm(b,a,b);
        }
}

int main()
{
    fin>>T;
    /*for(i=1;i<=T;++i)
        for(j=1;j<=7;++j)fin>>input[i][j];*/
    for(k=1;k<=T;++k)
    {
        /*X=input[k][1];
        Y=input[k][2];
        Z=input[k][3];
        A=input[k][4];
        B=input[k][5];
        C=input[k][6];
        N=input[k][7];*/
        fin>>X>>Y>>Z>>A>>B>>C>>N;

        mat[0][0]=mat[0][1]=mat[1][1]=mat[2][0]=0;
        mat[1][0]=mat[2][1]=1;
        mat[0][2]=C;
        mat[1][2]=B;
        mat[2][2]=A;

        alan(mat,k-3,MAT);
        fout<<(X*MAT[0][2]%MOD+Y*MAT[1][2]%MOD+Z*MAT[2][2]%MOD)%MOD;
        fout<<'\n';
        /*for(i=0;i<3;++i)
        {
            for(j=0;j<3;++j)fout<<MAT[i][j]<<' ';
            fout<<'\n';
        }*/

    }
        return 0;
}