#include <fstream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define INF 0x3f3f3f3f
#define mod 666013

using namespace std;

int a[4][4],b[4][4];
int t,x,y,z,q,w,e,n;
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(int count = 1; count <= t; ++count){
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&q,&w,&e,&n);
        a[1][1] = x;a[1][2] = y; a[1][3] = z;
        b[1][1] = e;b[2][1] = w; b[3][1] = q;
        n -= 2;
        while(n){
            n--;
            int aux = ((a[1][1] % mod*b[1][1] % mod) % mod + (a[1][2] % mod*b[2][1] % mod) % mod + (a[1][3] % mod*b[3][1] % mod) % mod) % mod;
            a[1][1] = a[1][2];
            a[1][2] = a[1][3];
            a[1][3] = aux;
        }
        printf("%d\n",a[1][3] % mod);
    }
    return 0;
}