AT_m_solutions2019_e Product of Arithmetic Progression

[problemUrl]: https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e 以下のような、$ 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 $ 個目の問いに対する答えを出力せよ。

### 制約 - $ 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 $ で割った余りを求めることをお忘れなく。