#include <fstream>
#define mod 666013
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
int n,a,b,c,x,y,z,t,p;
void prod (int b[3][3],int a[3][3])
{
    int c[3][3]= {{0,0,0},{0,0,0}};
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
            int sum=0;
            for (int g=0; g<3; g++)
                sum=(sum+1ll*a[g][j]*b[i][g])%mod;
            c[i][j]=sum;
        }
    }
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
            a[i][j]=c[i][j];
    }
}
int main()
{
    fin>>t;
    while (t--)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        int mat[3][3]={{z,0,0},{y,0,0},{x,0,0}};
        int fib[3][3]={{a,b,c},{1,0,0},{0,1,0}};
        n-=2;
        for (p=0; (1<<p)<=n; p++)
        {
            if ((n>>p)&1)
                prod (fib,mat);
            prod (fib,fib);
        }
        fout<<mat[0][0]<<"\n";
    }
    return 0;
}