問題
長さ $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$
入出力例
入力例１
6 2 3 5 4 3 1 3 1 6 2 3 3 5
出力例１
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$
が答えである。
入力例２
10 990125110 880796054 381171333 798502360 961789629 210036579 2335859 10827773 506506122 39805128 6 6 7 8 9 7 8 5 8 2 5 6 8
出力例２
829952056 273735975 150834963 776018300 126001326 400345564