#include <fstream>
using namespace std;
long long modp(long long a)
{
    if (a>0)
        return a;
    return -a;
}
long long exp(int n,long long e)
{
    if (e<=1)
        return n;
    long long rez=exp(n,e>>1);
    rez=(rez*rez)%666013;
    if (e&1)
        rez*=n;
    return rez%666013;
}
int main()
{
    int i,x;
    long long k,p;
    long long n;
    ifstream f1("invazie.in");
    ofstream f2("invazie.out");
    f1>>x;
    for (i=0;i<x;++i)
    {
        f1>>k>>p>>n;
        if (!n)
        {
            f2<<"1\n";
            continue;
        }
        p%=666013;
        k%=666013;
        f2<<((exp((k+p)%666013,n)-exp(modp(k-p),n))>>1)<<'\n';
    }
    f1.close();
    f2.close();
    return 0;
}