#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define MOD 1000003
using namespace std;
typedef long long ll;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

inline ll fastpow(ll bas, ll ex){
	register ll res = 1; bas %= MOD;
	for(; ex; ex >>= 1, bas = bas * bas % MOD) if(ex & 1) res = res * bas % MOD;
	return res;
}

int Q, fac[1000005] = {1, 1}, ifac[1000005] = {1, 1}, inv[1000005] = {1, 1};

int main(){
	getint(Q);
	for(register int i = 2; i < MOD; i++){
		fac[i] = fac[i - 1] * (ll)i % MOD;
		inv[i] = (MOD - MOD / i) * (ll)inv[MOD % i] % MOD;
		ifac[i] = ifac[i - 1] * (ll)inv[i] % MOD;
	}
	while(Q--){
		int x, d, n; getint(x), getint(d), getint(n);
		if(d == 0) printf("%lld\n", fastpow(x, n));
		else{
			x = x * (ll)inv[d] % MOD;
			if(x == 0 || x + n - 1 >= MOD) puts("0");
			else printf("%lld\n", fac[x + n - 1] * (ll)ifac[x - 1] % MOD * fastpow(d, n) % MOD);
		}
	}
	return 0;
}
### Prompt

Your challenge is to write 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define MOD 1000003
using namespace std;
typedef long long ll;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

inline ll fastpow(ll bas, ll ex){
	register ll res = 1; bas %= MOD;
	for(; ex; ex >>= 1, bas = bas * bas % MOD) if(ex & 1) res = res * bas % MOD;
	return res;
}

int Q, fac[1000005] = {1, 1}, ifac[1000005] = {1, 1}, inv[1000005] = {1, 1};

int main(){
	getint(Q);
	for(register int i = 2; i < MOD; i++){
		fac[i] = fac[i - 1] * (ll)i % MOD;
		inv[i] = (MOD - MOD / i) * (ll)inv[MOD % i] % MOD;
		ifac[i] = ifac[i - 1] * (ll)inv[i] % MOD;
	}
	while(Q--){
		int x, d, n; getint(x), getint(d), getint(n);
		if(d == 0) printf("%lld\n", fastpow(x, n));
		else{
			x = x * (ll)inv[d] % MOD;
			if(x == 0 || x + n - 1 >= MOD) puts("0");
			else printf("%lld\n", fac[x + n - 1] * (ll)ifac[x - 1] % MOD * fastpow(d, n) % MOD);
		}
	}
	return 0;
}
```