#include <fstream>
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
long long a, b, c, z, x, y, n, t, temp, zile;

using namespace std;

int main()
{
    fin >> t;
    for(int k = 0; k < t ; ++ k)
    {
        fin >> x >> y >> z >> a >> b >> c >> n;
        while(zile < n - 2)
        {
            temp = a * z + b * y + c * x;
            a = b;
            b = c;
            c= temp;
            ++zile;
            if(zile > 666013) zile %= 666013;
        }
        fout << c << endl;
        zile = 0;
    }
    return 0;
}