#include <fstream>
using namespace std;

#define nr 666013

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

unsigned long long a,b,c;
unsigned long long z[4];

int main()
{
    int set,i,n,t;
    in>>t;
    for(set=1;set<=t;set++)
    {
        in>>z[1]>>z[2]>>z[3]>>a>>b>>c>>n;
        for(i=3;i<=n;i++)
        {
            z[0]=z[1];
            z[1]=z[2];
            z[2]=z[3];
            z[3]=c*z[0]+b*z[1]+a*z[3];
            z[3]=z[3]%nr;
        }
        out<<z[3]<<'\n';
    }
    return 0;
}