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

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

int dp[5];
int Calc[max];

int inmultire(int number, int times) {
    int cc = 1;
    Calc[cc] = number;
    while(cc*2 <= times) {
        number = ((number % kMod) + (number % kMod)) % kMod;
        cc *= 2;
        Calc[cc] = number;
    }

    int j = cc/2;
    while(j != 0) {
        if(cc + j <= times) {
            number = (number + Calc[j]) % kMod;
            cc += j;
        } else {
            j = j/2;
        }
    }
    return number;
}

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] += ((inmultire(dp[2],A) + inmultire(dp[1],B)) % kMod + inmultire(dp[0],C)) % 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;
}