配点 : $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$ 個目の問いに対する答えを出力せよ。

2
7 2 4
12345 67890 2019

9009
916936

最初のクエリに対し、答えは $7 \times 9 \times 11 \times 13 = 9009$ です。 積を $1,000,003$ で割った余りを求めることをお忘れなく。