#include <iostream>
#include <fstream>
#define mod 666013
#define ll long long
using namespace std;

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

int answear(int x, int y, int z, int a, int b, int c, int n)
{
    int ans;
    x %= mod;
    y %= mod;
    z %= mod;
    ans = z;
    n -= 2;
    while(n)
    {
        ans = (a * z)  + (b * y)  + (c * x);
        //cout<<a <<'*' <<z<<'+'<<b<<'*'<<y<<'+'<<c<<'*'<<x<<endl;
        x = y;
        y = z;
        z = ans;
        //cout<<ans<<' '<<n<<endl;
        --n;
    }
    //cout<<endl;
    return ans;
}
int main()
{
    int x, y, z, a, b, c, n, t;
    fin>>t;

    for(int i = 1; i <= t; ++i)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        fout<<answear(x, y, z, a, b, c, n)<<'\n';
    }
    return 0;
}