#include <iostream>
using namespace std;
int v1[3], vc[3], v2[][3] = { {0, 0, 10}, {1, 0, 10}, {0, 1, 10} };
long long int n, a, b, c, x, y, z, f;
void inmultire(int f)
{
    while (--f)
    {
        for (int i = 0; i < 3; i++)
        {
            vc[i] = v1[i];
            v1[i] = 0;
        }
        for (int i = 0; i < 3 ; i++)
        {
            for (int ii = 0; ii < 3; ii++)
            {
                v1[i] += v2[ii][i] * vc[ii];
                v1[i] %= 666013;
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y >> z >> a >> b >> c >> f;
        v2[2][2] = a;
        v2[1][2] = b;
        v2[0][2] = c;
        v1[0] = x;
        v1[1] = y;
        v1[2] = z;
        inmultire(f-1);
        cout << v1[2] <<'\n';
    }
}