#include <fstream>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
unsigned nr=666013;

int main()
{
    int m,x,y,z,a,b,c,n,s=0,j,i;
    fin>>m;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        a%=nr;
        b%=nr;
        c%=nr;
        x%=nr;
        s=(a*z%nr+b*y%nr+c*x%nr)%nr;
        for(j=3;j<n;j++)
        {
            x=y;
            y=z;
            z=s;
            s=(a*z%nr+b*y%nr+c*x%nr)%nr;
        }
        fout<<s<<'\n';
        s=0;
    }
    return 0;
}