問題文

「何度も何度も何度も何度も何度も何度も夏を超えたから...」

正整数$a,b,c$が与えられます． また，関数$f$を$f: \Z \to \Z, f(x)=ax^{2}+bx+c, x \in \Z$で定義します($\Z$は整数全体の集合を表します)．

以下の問いに$Q$回答えてください． 問$i$の形式は以下の通りです．

• 問$i:$ 非負整数$n_i, x_i$が与えられます．$f^{(n_i)}(x_i)$を求めてください． ここで，$f^{(n)}$は関数$f$の$n$回合成したものを表します．

12/29 22:11追記
この問題では関数の合成回数を$f^{(0)}(x)=f(x),f^{(1)}(x)=f(f(x)),f^{(2)}(x)=f(f(f(x)))$のように定義します． 詳しくは入出力例を参考にしてください．

答えは非常に大きくなることがあるので，$(10^5+3)$で割った余りを出力してください．

制約

• $1 \leq a,b,c \leq 10^9$
• $1 \leq Q \leq 10^5$
• $0 \leq n_i,x_i \leq 10^9$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを$Q$行に出力せよ．$i$行目には問$i$の答えを$(10^5+3)$で割った余りを出力せよ．

サンプル

1 2 3
4
0 1
1 1
2 1
3 1

6
51
2706
27632

この問題では$f(x)=x^2 + 2x +3$です．よって各問の答えは

• $f^{(0)}(1) = f(1) = 1^2 + 2 \times 1 + 3 = 6$
• $f^{(1)}(1) = f(f(1)) = 6^2 + 2 \times 6 + 3 = 51$
• $f^{(2)}(1) = f(f(f(1))) = 51^2 + 2 \times 51 + 3 = 2706$
• $f^{(3)}(1) = f(f(f(f(1)))) = 2706^2 + 2 \times 2706 + 3 = 7327851$

となるため，それを$(10^5+3)$で割った余りである数値をそれぞれ出力します．