#include <fstream>
#define HATZJHON 666013
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

long long n,t,a,b,c,j;
unsigned long long int x,y,z,s;
int main()
{
    fin>>t;
    for(int i = 1;i <= t;i++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        if(n == 0) {fout<<x<<'\n';continue;}
        if(n == 1) {fout<<y<<'\n';continue;}
        if(n == 2) {fout<<z<<'\n';continue;}
        s = 0;
        s = (a * z + b * y + c * x) % HATZJHON;
        x = y; y = z; z = s;
        int j = 1;
        while(j <= n - 3)
        {
            s = (a * z + b * y + c * x) % HATZJHON;
            x = y; y = z; z = s;
            j++;
        }
        fout<<s<<'\n';
    }
    return 0;
}