#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;

int main() 
{
    ifstream cin("iepuri.in");
    ofstream cout("iepuri.out");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int q; cin >> q;
    while (q --)
    {
        int x, y, z, a, b, c, n; cin >> x >> y >> z >> a >> b >> c >> n;
        int dp0, dp1, dp2;
        dp0 = x;
        dp1 = y;
        dp2 = z;
        int aux = 0;
        for (int i = 3; i <= n; i ++)
        {
            aux = dp2;
            dp2 = dp2 * a  + dp1 * b + dp0 * c;
            dp2 %= MOD;
            dp0 = dp1;
            dp1 = aux;
        }
        cout << dp2 << '\n';
    }
}