#include <iostream>
#include <fstream>
using namespace std;

#define kMod 666013
#define zile 2000000001
#define max 1001

int dp[5];

int main()
{
    int T;
    int X,Y,Z,A,B,C;
    unsigned long long N;
    ifstream in("iepuri.in");
    ofstream out("iepuri.out");
    in >> T;

    for(int i = 1; i <= T; ++i) {
        in >> X >> Y >> Z >> A >> B >> C >> N;
        dp[0] = X;
        dp[1] = Y;
        dp[2] = Z;

        for(unsigned long long j = 3; j <= N; ++j) {
            dp[3] += (A * dp[2] + B*dp[1] + C * dp[0]) % kMod;
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = dp[3];
            dp[3] = 0;
        }
        out << dp[2] << '\n';
    }

    in.close();
    out.close();
    return 0;
}