#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int mod=666013;
int x,y,z,a,b,c,n;

int main()
{
    int t;
    fin>>t;
    while(t--){
        fin>>x>>y>>z>>a>>b>>c>>n;
        int s;
        for(int i=3;i<=n;i++){
            s=x*a+y*b+z*c;
            if(i==n) fout<<s%mod<<endl;
            else{
                c=b;
                b=a;
                a=s;
            }
        }
    }
    return 0;
}