#include<fstream>   
using namespace std;   
int main()   
{   
    ifstream in("iepuri.in");   
    ofstream out("iepuri.out");   
    long t,x,j,y,z,a,b,c,w,i,n;   
    in>>t;   
    for (j=1;j<=t;j++)   
    {in>>x>>y>>z>>a>>b>>c>>n;   
    for (i=3;i<=n;i++)   
    {w=z*a+y*b+x*c;   
    x=y;   
    y=z;   
    z=w;   
    if (z>=666013) z=z%666013;}   
    out<<z<<endl;}   
    in.close();   
    out.close();   
    return 0;   
}