#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll p[2000010],hell=1000003;
ll exp(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y&1)
        res=(res*x)%hell;
        y>>=1;
        x=(x*x)%hell;
    }
    return res;
}
void solve(){
    ll x,d,n;
    cin>>x>>d>>n;
    if(d==0){
        cout<<exp(x,n)<<endl;
        return;
    }
    else if(n>hell){
        cout<<"0\n";
        return;
    }
    x*=exp(d,hell-2);
    x%=hell;
    if(x==0){
        cout<<"0\n";
        return;
    }
    ll res=(exp(d,n)*p[x+n-1])%hell;
    res%=hell;
    res*=exp(p[x-1],hell-2);
    res%=hell;
    cout<<res<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    p[0]=1;
    for(ll i=1;i<2000010;i++)
    p[i]=(i*p[i-1])%hell;
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++)
    solve();
}

### Prompt

Generate a CPP solution to the following problem:

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;
typedef long long int ll;
ll p[2000010],hell=1000003;
ll exp(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y&1)
        res=(res*x)%hell;
        y>>=1;
        x=(x*x)%hell;
    }
    return res;
}
void solve(){
    ll x,d,n;
    cin>>x>>d>>n;
    if(d==0){
        cout<<exp(x,n)<<endl;
        return;
    }
    else if(n>hell){
        cout<<"0\n";
        return;
    }
    x*=exp(d,hell-2);
    x%=hell;
    if(x==0){
        cout<<"0\n";
        return;
    }
    ll res=(exp(d,n)*p[x+n-1])%hell;
    res%=hell;
    res*=exp(p[x-1],hell-2);
    res%=hell;
    cout<<res<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    p[0]=1;
    for(ll i=1;i<2000010;i++)
    p[i]=(i*p[i-1])%hell;
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++)
    solve();
}

```