#include <fstream>
#define M 666013
using namespace std;

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

int main()
{
    long long x,y,z,a,b,c,nrset,n;
    cin>>nrset;
    for(int i=1; i<=nrset; ++i)
    {
        cin>>x>>y>>z>>a>>b>>c>>n;
        for(int j=3; j<=n; ++j)
        {
            long long t=(a*z+b*y+c*x)%M;
            x=y; y=z; z=t;
        }
        cout<<z%M<<"\n";

    }

    return 0;
}