#include <fstream>
#define nr 666013

using namespace std;

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

int main()
{
    int n,i;
    unsigned long long d;
    short a,b,c,j,t;
    int x,y,z;
    f>>t;
    for(j=1;j<=t;j++)
    {
    f>>x>>y>>z>>a>>b>>c>>n;
    x=x%nr;
    y=y%nr;
    z=z%nr;
    a=a%nr;
    b=b%nr;
    c=c%nr;
    for(i=3;i<=n;i++)
    {
        d=x*c+y*b+z*a;
        d=d%nr;
        x=y;
        y=z;
        z=d;
    }
    g<<z<<'\n';
    }
    return 0;
}