#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;
            x = y;
            y = z;
            z = temp;
            ++zile;
            if(z > 666013) {z %= 666013; y %= 666013; x %= 666013;}
        }
        fout << z << endl;
        zile = 0;
    }
    return 0;
}