#include <cstdio>
#define MOD 666013
using namespace std;

int t, n, k, p;
inline void euclid(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1; y = 0;
        return ;
    }
    int x0, y0;
    euclid(b, a % b, x0, y0);
    x = y0;
    y = x0 - y0 * (a / b);
}
int main()
{
    freopen("invazie.in", "r", stdin);
    freopen("invazie.out", "w", stdout);
    scanf("%d", &t);
    for(int i = 1; i <= t ; ++i){
        scanf("%d%d%d", &k, &p, &n);
        int Sum = 1, Dif = 1, aux1 = (k + p), aux2 = (k - p);
        for(int i = 0; (1 << i) <= n ; ++i){
            if(((1 << i) & n) > 0) {
                Sum = (Sum * aux1) % MOD;
                Dif = (Dif * aux2) % MOD;
            }
            aux1 = (aux1 * aux1) % MOD;
            aux2 = (aux2 * aux2) % MOD;
        }
        int inv = 0, ins;
        euclid(2, MOD, inv, ins);
        if(inv <= 0) inv = (inv % MOD) + MOD;
        printf("%d\n", ((Sum + Dif) * inv) % MOD);
    }
    return 0;
}