H. Prefix Tower
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
woodpecker 1
Merzbrow

Charlie is writing a mixing software, which takes in an array of records $$$a$$$ with $$$n$$$ elements. Charlie also wants to mix the tracks together. He has devised this clever algorithm (that also produces great soundtracks) called the prefix mixing operation $$$p(a)$$$ as follows:

  • $$$a[i] := a[i - 1] \times a[i]\bmod {10^9 + 7}$$$, for each $$$1 \lt i \leq n$$$ in order.

For example, for the array $$$a = [5,7,10]$$$, the prefix operation would produce $$$p(a) = [5,35,350]$$$, since the multiplication is done in succession. The $$$k$$$-th prefix operation $$$p^{k}$$$ is the prefix operation applied $$$k$$$ times. For example, for $$$k=2$$$, $$$p^{2}(a)$$$ would be defined as $$$p(p(a))$$$, and $$$p^{3}(a) = p(p(p(a)))$$$.

Unfortunately, the current software rendering this transformation takes a long time to run, so Charlie needs your help to fix it. In order to do this, Charlie wants to know arbitrary elements for the array $$$p^{k_i}(a)$$$. Can you help him find them?

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

For each test case, the first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n, q \leq 1000$$$) — the number of elements in the array $$$a$$$ and the number of queries, respectively.

The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i\leq 10^9$$$).

The next $$$q$$$ lines each contain two space-separated integers $$$k_i$$$ and $$$x_i$$$ ($$$1\leq k_i\leq 1000, 1\leq x_i\leq n$$$) — which is the $$$i$$$-th query asking for the answer of $$$p^{k_i}(a)[x_i]$$$.

It is guaranteed that the sum of all $$$q$$$ over all test cases is at most $$$1000$$$.

There is no additional bound on the sum of all $$$n$$$ or $$$x_i$$$.

Output

For each query in each test case, output one integer — the value of $$$p^{k_i}(a)[x_i]$$$

Example
Input
2
5 3
1 2 3 4 5
1 1
1 2
2 4
5 4
5 4 3 2 1
1 1
1 2
1 3
2 3
Output
1
2
288
5
20
60
6000
Note

For the first test case: $$$p^{1}(a) = [1, 2, 6, 24, 120]$$$ and $$$p^{2}(a) = [1, 2, 12, 288, 34560]$$$