#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e6+3; // prime number
ll getPow(ll a,ll p){
  ll ret = 1,cp = a;
  while(p){
    if(p&1) ret = (ret*cp)%MOD;
    p >>= 1;
    cp = (cp*cp)%MOD;
  }
  return ret;
}
ll getInverse(ll a){
  return getPow(a,MOD-2)%MOD;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<ll> inv(MOD,1),fact(MOD,1);
  for(ll i = 2; i < MOD; ++i){
    inv[i] = getInverse(i);
    fact[i] = (i*fact[i-1])%MOD;
  }
  ll q,x,d,n;
  cin >> q;
  while(q--){
    cin >> x >> d >> n;
    if(d == 0) cout << getPow(x,n);
    else if(x == 0) cout << 0;
    else{
      ll X = (x*inv[d])%MOD;
      if(X+n-1 >= MOD) cout << 0;
      else{
        ll ret = (fact[X+n-1]*inv[fact[X-1]])%MOD;
        cout << (ret*getPow(d,n))%MOD;
      }
    }
    cout << '\n';
  }
  return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

Consider the following arithmetic progression with n terms:

* x, x + d, x + 2d, \ldots, x + (n-1)d



What is the product of all terms in this sequence? Compute the answer modulo 1\ 000\ 003.

You are given Q queries of this form. In the i-th query, compute the answer in case x = x_i, d = d_i, n = n_i.

Constraints

* 1 \leq Q \leq 10^5
* 0 \leq x_i, d_i \leq 1\ 000\ 002
* 1 \leq n_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


Q
x_1 d_1 n_1
:
x_Q d_Q n_Q


Output

Print Q lines.

In the i-th line, print the answer for the i-th query.

Example

Input

2
7 2 4
12345 67890 2019


Output

9009
916936

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e6+3; // prime number
ll getPow(ll a,ll p){
  ll ret = 1,cp = a;
  while(p){
    if(p&1) ret = (ret*cp)%MOD;
    p >>= 1;
    cp = (cp*cp)%MOD;
  }
  return ret;
}
ll getInverse(ll a){
  return getPow(a,MOD-2)%MOD;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<ll> inv(MOD,1),fact(MOD,1);
  for(ll i = 2; i < MOD; ++i){
    inv[i] = getInverse(i);
    fact[i] = (i*fact[i-1])%MOD;
  }
  ll q,x,d,n;
  cin >> q;
  while(q--){
    cin >> x >> d >> n;
    if(d == 0) cout << getPow(x,n);
    else if(x == 0) cout << 0;
    else{
      ll X = (x*inv[d])%MOD;
      if(X+n-1 >= MOD) cout << 0;
      else{
        ll ret = (fact[X+n-1]*inv[fact[X-1]])%MOD;
        cout << (ret*getPow(d,n))%MOD;
      }
    }
    cout << '\n';
  }
  return 0;
}
```