//
//  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 a[3][3],long long b[3][3]){
    int i,j;
    long long aux[4][4];
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {aux[i][j]=0;
            for(int q=0;q<3;q++)
                aux[i][j]+=a[i][q]*b[q][j]%MOD;}
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            a[i][j]=aux[i][j];}
void exp(long long T[3][3],int n){
    if(n == 0 || n == 1)return;
    long long M[3][3] = {{A,1,0},{B,0,1},{C,0,0}};
    exp(T,n/2);
    Mult(T,T);
    if(n % 2)
        Mult(T,M);
}
long long tribonacci(int n){
    long long T[3][3] = {{A,1,0},{B,0,1},{C,0,0}};
    if(n == 0 || n == 1){
        return 0;
    }
    else {
        exp(T, n - 2);
        return ((T[0][0] * z) % MOD + (T[1][0] * y) % MOD + (T[2][0] * 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;
}