题目描述

以下のような、$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$ の場合の答えを計算してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$Q$ $x_1$ $d_1$ $n_1$ $:$ $x_Q$ $d_Q$ $n_Q$

输出格式

$Q$ 行出力せよ。

$i$ 行目に、$i$ 個目の問いに対する答えを出力せよ。

题目大意

给定 $q$ 组询问，每次输入三个数 $x,d,n$，求 $\prod\limits_{i = 0}^{n - 1} (x + i \times d) \bmod 1000003$。

2
7 2 4
12345 67890 2019

9009
916936

提示

制約

• $1\ \leq\ Q\ \leq\ 10^5$
• $0\ \leq\ x_i,\ d_i\ \leq\ 1,000,002$
• $1\ \leq\ n_i\ \leq\ 10^9$
• 入力中の値はすべて整数である。

Sample Explanation 1

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