/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
以下のような、n 項からなる等差数列を考えます。
- x, x + d, x + 2d, \ldots, x + (n-1)d
この数列のすべての項の積はいくつでしょうか？ その積を 1,000,003 で割った余りを計算してください。
この形式の問いが Q 個与えられます。 i 個目の問いでは、x = x_i, d = d_i, n = n_i の場合の答えを計算してください。
制約
- 1 \leq Q \leq 10^5
- 0 \leq x_i, d_i \leq 1,000,002
- 1 \leq n_i \leq 10^9
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
Q x_1 d_1 n_1 : x_Q d_Q n_Q
出力
Q 行出力せよ。
i 行目に、i 個目の問いに対する答えを出力せよ。
入力例 1
2 7 2 4 12345 67890 2019
出力例 1
9009 916936
最初のクエリに対し、答えは 7 \times 9 \times 11 \times 13 = 9009 です。 積を 1,000,003 で割った余りを求めることをお忘れなく。
Score : 600 points
Problem Statement
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.
Sample Input 1
2 7 2 4 12345 67890 2019
Sample Output 1
9009 916936
For the first query, the answer is 7 \times 9 \times 11 \times 13 = 9009. Don't forget to compute the answer modulo 1\ 000\ 003.