#include <cstdio>
#include <cstring>
using namespace std;
const long long MOD = 666013;
class matrice
{
private:
    int n , m;
    long long a[5][5];
public:
    matrice(int tn = 3 , int tm = 3 , long long x = 0 , long long y = 0 , long long z = 0)
    {
        memset(a , 0 , sizeof(a));
        if(tn == -1)
            n = m = 3;
        else
        {
            n = tn;
            m = tm;
            if(tn == 1)
            {
                a[1][1] = x;
                a[1][2] = y;
                a[1][3] = z;
            }
            else if(tn == 3 && x != 0)
            {
                a[2][1] = a[3][2] = 1;
                a[1][3] = z;
                a[2][3] = y;
                a[3][3] = x;
            }
            else
                a[1][1] = a[2][2] = a[3][3] = 1;
        }
    }
    matrice operator*(const matrice& b)
    {
        int i , j , k;
        matrice c(-1);
        c.n = n;
        c.m = b.m;
        for(i = 1 ; i <= c.n ; i ++)
            for(k = 1 ; k <= c.m ; k ++)
                for(j = 1 ; j <= m ; j ++)
                    c.a[i][k] = (c.a[i][k] + (a[i][j] * b.a[j][k]) % MOD) % MOD;
        return c;
    }
    void get_elem()
    {
        printf("%lld\n" , a[1][3]);
    }
};
matrice fast_pow(matrice a , int p)
{
    matrice aa;
    for( ; p ; p = (p >> 1))
    {
        if(p & 1)
            aa = aa * a;
        a = a * a;
    }
    return aa;
}
int main()
{
    freopen("iepuri.in" , "r" , stdin);
    freopen("iepuri.out" , "w" , stdout);
    int n , t , i;
    long long x , y , z , a , b , c;
    scanf("%d" , &t);
    for(i = 1 ; i <= t ; i ++)
    {
        scanf("%lld%lld%lld%lld%lld%lld%d" , &x , &y , &z , &a , &b , &c , &n);
        matrice m1(1 , 3 , x , y , z);
        matrice m2(3 , 3 , a , b , c);
        m2 = fast_pow(m2 , n - 2);
        m1 = m1 * m2;
        m1.get_elem();
    }
    return 0;
}