1273 - Range Product Query

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer もけ / x 9 / 統計 /


TLE
1sec
MLE
64MB
得点
100

問題

長さ $N$ の正整数列 $A$ が与えられる。
$i$ $(1 \leq i \leq N)$ 番目の要素は $a_i$ である。
$Q$ 回にわたって, $L_j, R_j$ $(1 \leq j \leq Q)$ が与えられるので、
$\large \displaystyle \prod_{k = L_j}^{R_j} a_k \bmod (10^9 + 7)$ を求めよ。

入力

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

$N$
$a_1$ $a_2$ $\ldots$ $a_N$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

出力

各クエリに対する答えを改行区切りで出力せよ。

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq a_i \leq 10^9$
  • $1 \leq Q \leq 10^5$
  • $1 \leq L_j \leq R_j \leq N$

入出力例

入力例1

6
2 3 5 4 3 1
3
1 6
2 3
3 5

出力例1

360
15
60

$1$ 回目のクエリは $L_j = 1, R_j = 6$ である。
よって、$(a_1 \times a_2 \times a_3 \times a_4 \times a_5 \times a_6) \bmod (10^9 + 7) \\ = (2 \times 3 \times 5 \times 4 \times 3 \times 1) \bmod (10^9 + 7) \\ = 360$ が答えである。


入力例2

10
990125110 880796054 381171333 798502360 961789629 210036579 2335859 10827773 506506122 39805128
6
6 7
8 9
7 8
5 8
2 5
6 8

出力例2

829952056
273735975
150834963
776018300
126001326
400345564