//
//  main.cpp
//  p2sah
//
//  Created by Radu Costache on 25/02/2018.
//  Copyright © 2018 Radu Costache. All rights reserved.
//

#include <fstream>

#define MOD 666013

using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

long long n,p,k,c = 3,a = 1,A,B,C,x,y,z;
void Mult(long long T[3][3],long long M[3][3]){
    long long a, b, c, d, e, f, g, h, i;
    a = (T[0][0] * M[0][0] + T[0][1] * M[1][0] + T[0][2] * M[2][0]) % MOD;
    b = (T[0][0] * M[0][1] + T[0][1] * M[1][1] + T[0][2] * M[2][1]) % MOD;
    c = (T[0][0] * M[0][2] + T[0][1] * M[1][2] + T[0][2] * M[2][2]) % MOD;
    d = (T[1][0] * M[0][0] + T[1][1] * M[1][0] + T[1][2] * M[2][0]) % MOD;
    e = (T[1][0] * M[0][1] + T[1][1] * M[1][1] + T[1][2] * M[2][1]) % MOD;
    f = (T[1][0] * M[0][2] + T[1][1] * M[1][2] + T[1][2] * M[2][2]) % MOD;
    g = (T[2][0] * M[0][0] + T[2][1] * M[1][0] + T[2][2] * M[2][0]) % MOD;
    h = (T[2][0] * M[0][1] + T[2][1] * M[1][1] + T[2][2] * M[2][1]) % MOD;
    i = (T[2][0] * M[0][2] + T[2][1] * M[1][2] + T[2][2] * M[2][2]) % MOD;
    T[0][0] = a;
    T[0][1] = b;
    T[0][2] = c;
    T[1][0] = d;
    T[1][1] = e;
    T[1][2] = f;
    T[2][0] = g;
    T[2][1] = h;
    T[2][2] = i;
}
void exp(long long T[3][3],int n){
    if(n == 0 || n == 1)return;
    long long M[3][3] = {{0,0,C},{1,0,B},{0,1,A}};
    exp(T,n/2);
    Mult(T,T);
    if(n % 2)
        Mult(T,M);
}
long long tribonacci(int n){
    long long T[3][3] = {{0,0,C},{1,0,B},{0,1,A}};
    if(n == 0 || n == 1){
        return 0;
    }
    else {
        exp(T, n - 2);
        return ((T[0][2] * z) % MOD + (T[1][2] * y) % MOD + (T[2][2] * x) % MOD) % MOD;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int T;
    f >> T;
    while(T--){
    f >> x >> y >> z >> A >> B >> C >> n;
        g << tribonacci(n) << '\n';
    }
    return 0;
}