Product of Ranges

以上の整数 と、 以上の整数 個からなる数列 が与えられる。

個のクエリ に対して、以下の式により定義される を で割ったあまりを求めよ。

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

N Q
A_1 A_2 ... A_N
l_1 r_1
l_2 r_2
...
l_N r_N

入力サイズが大きいため、Pythonでは入力に以下を指定してください。

import sys
input = sys.stdin.readline

個のクエリについて、 を 行で出力せよ。

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

6
24
120

個目のクエリでは を出力します。
個目のクエリでは を出力します。
個目のクエリでは を出力します。

8 3
31415 92653 58979 32384 62643 38327 95028 84197
1 3
2 7
1 8

741501342
924207616
583067047

あまりを取ることを忘れないようにしてください。