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

const int NMAX = 2e9, MOD = 666013;
int dp[NMAX];

int main() 
{
    ifstream cin("iepuri.in");
    ofstream cout("iepuri.out");
	int q; cin >> q;
    while (q --)
    {
        int x, y, z, a, b, c, n; cin >> x >> y >> z >> a >> b >> c >> n;
        dp[0] = x;
        dp[1] = y;
        dp[2] = z;
        for (int i = 3; i <= n; i ++)
        {
            dp[i] = dp[i - 1] * a + dp[i - 2] * b + dp[i - 3] * c;
            dp[i] %= MOD;
        }
        cout << dp[n] << '\n';
    }
}