#include <fstream>
#define MOD 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long dp[4][4], x, y, z, a, b, c, n, t;
void read()
{
    fin>>x>>y>>z>>a>>b>>c>>n;
    dp[1][1]=0, dp[1][2]=0, dp[1][3]=c;
    dp[2][1]=1, dp[2][2]=0, dp[2][3]=b;
    dp[3][1]=0, dp[3][2]=1, dp[3][3]=a;
}
void solve(long long a[4][4], long long pow)
{
    long long c[4][4], b[4][4], i, j, k;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            b[i][j]=a[i][j];
    if(pow>1)
    {
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
            {
                a[i][j]=0;
                for(k=1;k<=3;k++)
                    a[i][j]=(a[i][j]+(1LL*b[i][k]*b[k][j])%MOD)%MOD;
            }
        if(pow%2==0)
            solve(a, pow/2);
        else
        {
            solve(a, (pow-1)/2);
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    c[i][j]=a[i][j];
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                {
                    a[i][j]=0;
                    for(k=1;k<=3;k++)
                        a[i][j]=(a[i][j]+(1LL*b[i][k]*c[k][j])%MOD)%MOD;
                }
        }
    }
}
void write()
{
    fout<<(1LL*x*dp[1][3]+1LL*y*dp[2][3]+1LL*z*dp[3][3])%MOD<<'\n';
}
int main()
{
    fin>>t;
    while(t--)
    {
        read();
        solve(dp, n-2);
        write();
    }
    return 0;
}