#include <fstream>
#include <string.h>
#define MOD 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
int t, x, y, z, a, b, c, i, j, k, n, put;
long long cstMat[4][4], tmp[4][4], res[4][4], res2[4][4];
int main()
{
    f>>t;
    for (; t--; ) {
        f>>x>>y>>z>>a>>b>>c>>n;
        put=n-2;
        memset(res, 0, sizeof(res));
        memset(cstMat, 0, sizeof(cstMat));
        res[1][1]=1;
        res[2][2]=1;
        res[3][3]=1;
        cstMat[2][1]=1;
        cstMat[3][2]=1;
        cstMat[1][3]=c;
        cstMat[2][3]=b;
        cstMat[3][3]=a;
        while (put!=0) {
            if (put%2==1) {
                for (i=1; i<=3; i++)
                    for (j=1; j<=3; j++)
                        for (k=1; k<=3; k++)
                            tmp[i][j]=(tmp[i][j]+res[i][k]*cstMat[k][j])%MOD;
                memcpy(res, tmp, sizeof(tmp));
            }
            memset(tmp, 0, sizeof(tmp));
            for (i=1; i<=3; i++)
                for (j=1; j<=3; j++)
                    for (k=1; k<=3; k++)
                        tmp[i][j]=(tmp[i][j]+cstMat[i][k]*cstMat[k][j])%MOD;
            memcpy(cstMat, tmp, sizeof(tmp));
            memset(tmp, 0, sizeof(tmp));
            put/=2;
        }
        res2[1][1]=x;
        res2[1][2]=y;
        res2[1][3]=z;
        for (i=1; i<=1; i++)
            for (j=1; j<=3; j++)
                for (k=1; k<=3; k++)
                    tmp[i][j]=(tmp[i][j]+res2[i][k]*res[k][j])%MOD;
        memcpy(res2, tmp, sizeof(tmp));
        memset(tmp, 0, sizeof(tmp));
        g<<res2[1][3]<<"\n";
    }
    return 0;
}