#include <iostream>
#include <fstream>
const int mod=666013;
using namespace std;
int zi[3], iepuri[4];

int calcul(int n)
{
    iepuri[3]=iepuri[0]*zi[2]+iepuri[1]*zi[1]+iepuri[2]*zi[0];
    while (n)
    {
        iepuri[0]=iepuri[1];
        iepuri[1]=iepuri[2];
        iepuri[2]=iepuri[3];
        iepuri[3]=(iepuri[0]*zi[2]+iepuri[1]*zi[1]+iepuri[2]*zi[0])%mod;
        n--;
    }
    return iepuri[3];
}

int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    int t;
    f>>t;
    for (int i=1; i<=t; i++)
    {
        int n;
        f>>iepuri[0]>>iepuri[1]>>iepuri[2];
        f>>zi[0]>>zi[1]>>zi[2];
        f>>n;
        g<<calcul(n-3)<<"\n";
    }
    return 0;
}