#include <fstream>
#include <stdlib.h>
using namespace std;

long long n;
const long long mod=666013;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

int main()
{
    int t,i,x,y,z,a,b,c,n,nr,nou,ct;
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>x>>y>>z>>a>>b>>c>>n;
        nr=0;
        ct=3;
        while(ct<=n)
        {
            nou=(a*z+b*y+c*x)%mod;
            x=y;
            y=z;
            z=nou;
            ct++;
        }
        cout<<z%mod<<'\n';
    }
    return 0;
}