#include <iostream>
#include <fstream>
#define m 666013;
using namespace std;

int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    int t, x, y, z, a, b, c, n, i, j, v[20000000];
    f >> t;
    for(i=1;i<=t;i++)
    {
        f >> x >> y >> z >> a >> b >> c >> n;
        v[0]=x;
        v[1]=y;
        v[2]=z;
        for(j=3;j<=n;j++)
        {
            v[j]=(v[j-1]*a+v[j-2]*b+v[j-3]*c)%m;
        }
        g << v[n] << endl;
    }
    f.close();
    g.close();
    return 0;
}