#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;
        s = ((a * z) % HATZJHON + (b * y) % HATZJHON + (c * x) % HATZJHON) % HATZJHON;
        x = y; y = z; z = s;
        int j = 1;
        while(j <= n - 3)
        {
            s =  ((a * z) % HATZJHON + (b * y) % HATZJHON + (c * x) % HATZJHON) % HATZJHON;
            x = y; y = z; z = s;
            j++;
        }
        fout<<s<<'\n';
    }
    return 0;
}