#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ll long long
#define ALL(a)  (a).begin(),(a).end()

#define pb(a) push_back(a)
#define MOD 1000003


vector<ll> stk;//l～rまでリダクションしたいときの

//a/b mod c
ll moddiv(ll a,ll b){
	ll x0=MOD,x1=b,x2,n0=0LL,n1=1LL,n2,t=a%b,m,ans;
	if (t==0) return a/b;
		for(int i=0;i<900;i++){
      m=x0/x1;
      x2=x0-x1*m;
      n2=(n0-m*n1)%MOD;
      if (x2==1){
        ans=(n2+MOD)%MOD;
        break;
      }
      x0=x1;x1=x2;
      n0=n1;n1=n2;
    }
	return (a+((t*ans)%MOD)*b-t)/b;
}
//剰余の割ざん

//aのn乗 mod c
ll expmod(ll a,ll n){
  ll ans=1LL,aa=a,beki=n;
  for(int i=0;i<64;i++){
    if (beki%2==1) ans=ans*aa%MOD;
    aa=aa*aa%MOD;
    beki/=2;
    if (beki==0)break;
  }
  return ans;
}








////////////////////////////////////////////////////////////////////////O(N logN)リダクション
bool Chkbit(int num,int n){
  return ((num>>n)%2==1);
}

int Log2u(int num){
  //自分含むより高い次にくる2^NとなるNを返す
  int rsznum=num-1;
  int beki=0;
  for(int i=0;i<32;i++){
    if (rsznum==0){
      beki=i;
      break;
    }
    rsznum/=2;
  }
  return beki;
}


ll Makestk_f0(ll a1,ll a2){
  return a1*a2%MOD;//●●●●●●●●●●●●●●●●●●●●●●●
}

void Makestk(ll num){
  int beki=Log2u(num)+1;
  int rsznum=1<<beki;
  stk.resize(rsznum);
  //初期値設定●●●●●●●●●●●●●●●●●●●●●●●
  for(int i=0;i<num;i++){
    stk[i]=(ll)i;
  }
  //初期値0埋め●●●●●●●●●●●●●●●●●●●●●●●
  for(int i=num;i<rsznum/2;i++){
    stk[i]=1LL;
  }

  //2こ1にまとめていく。1レイヤーごと半分になっていく
  //初期レイヤー含めずあとbeki個必要
  int ofst=rsznum/2;
  int ofstp=0;//1個まえのofst
  for(int j=beki-2;j>=0;j--){
    int bk1=1<<j;
    for(int i=0;i<bk1;i++){
      stk[ofst+i]=Makestk_f0(stk[ofstp+i*2],stk[ofstp+i*2+1]);
    }
    ofstp=ofst;
    ofst+=bk1;
  }
}

//stk前半データに対し0～n-1までのリダクション施行した結果を返す
ll Reduc0(int n){
  int nn=n;
  ll ans=1LL;//●●●●●●●●●●●●●●●●●●●●●●●
  int sz=stk.size()/2;
  int ofst=0;
  int beki=Log2u(sz);
  for(;nn>0;nn>>=1){
    if (nn%2==1){
        ans=Makestk_f0(ans,stk[ofst+nn-1]);
    }
    ofst+=1<<beki;
    beki--;
  }
  return ans;
}

//stk前半データに対しl～r-1までのリダクション施行した結果を返す
ll Reduc1(int l,int r){
  int nn=r;
  int mm=l;
  ll ans=1LL;//●●●●●●●●●●●●●●●●●●●●●●●
  int sz=stk.size()/2;
  int ofst=0;
  int beki=Log2u(sz);
  int i=0;
  for(int i=0;(nn+mm)>0;i++){
    if (nn%2==1){
        if (nn-1>=mm){
          ans=Makestk_f0(ans,stk[ofst+nn-1]);
          nn--;
        }
    }
    
    if (mm%2==1){
        if (mm<nn){
          ans=Makestk_f0(ans,stk[ofst+mm]);
          mm++;
        }
    }

    nn>>=1;
    mm>>=1;
    ofst+=1<<(beki-i);
  }
  return ans;
}
////////////////////////////////////////////////////////////////////////O(N logN)リダクション




int main() {
  Makestk(MOD);

  ll q,x,d,n,y;
  ll ans=1LL;
  cin>>q;
  REP(i,q){
    cin>>x>>d>>n;
    if (d==0){
      cout<<(expmod(x,n)%MOD)<<endl;
      continue;
    }
    y=moddiv(x,d);
    //y～y+n-1までリダクション掛け算
    ll loop=(y+n-1)/MOD;
    if (loop!=0){
      cout<<0<<endl;
      continue;
    }

    ll red=Reduc1(y,y+n);
    ans=red*expmod(d,n)%MOD;
    cout<<ans<<endl;
  }

  return 0;
}

Measured memory_bytes: 17280