H. House Rules
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Somewhere along a famous beach in Rio de Janeiro, $$$n$$$ friends share a house (because how can you afford rent alone?). They all follow one sacred rule: always leave your shoes by the door when entering.

Each friend has $$$k$$$ pairs of shoes, and since they are too poor to afford a decent shoe rack, they decided to just draw lines on the ground to create $$$nk$$$ slots to place their pairs of shoes. The slot $$$i$$$ is at a distance of $$$i$$$ from the door, and initially contains a shoe from the person $$$a_i$$$.

Every day, each person selects a random pair of shoes they own and leaves the house in the morning. They all arrive in the afternoon in a random order, and place their shoes on the first slot available (closest to the door).

You need to answer $$$q$$$ queries. On each query, given two integers $$$x$$$ and $$$d$$$, calculate the expected average distance of all the pairs of shoes of person $$$x$$$ to the door after $$$d$$$ days. It can be shown that this answer can always be expressed as a fraction $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1}\mod (10^9+7)$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2\leq n \leq 10^5, 1\leq k \leq 10^5)$$$ — the number of friends and the number of pairs of shoes each of them owns. It is guaranteed that $$$n\cdot k \leq 5\cdot 10^5$$$.

The second line contains $$$n\cdot k$$$ integers $$$a_i$$$ $$$(1\leq a_i \leq n)$$$ — the owner of the shoe on the slot $$$i$$$ at the beginning.

The third line contains an integer $$$q$$$ $$$(1\leq q \leq 5\cdot 10^5)$$$ — the number of queries to answer.

The next $$$q$$$ lines contain each two integers $$$x$$$ and $$$d$$$ $$$(1\leq x\leq n, 0\leq d\leq 10^{18})$$$ — the person and the number of days for which you need to answer the query.

Output

For each query, print one integer — the expected average distance of the shoes of the person $$$x$$$ after $$$d$$$ days.

Examples
Input
3 1
1 2 3
5
1 0
2 6969694206969
1 420696969420
3 1
3 0
Output
1
2
2
2
3
Input
3 2
1 2 1 2 3 3
8
1 0
2 0
3 0
1 1
2 2
1 3
3 4
1 1000000000000000000
Output
2
3
500000009
750000008
375000006
812500009
625000008
763897687
Note

On the first example: We see that for $$$d = 0$$$, then the shoes will remain in the same spot, and so their distance to the door will remain the same. For the query $$$\{3\,\, 1\}$$$, when the people return to the house on day $$$1$$$, each shoe has an equal probability of staying in each position, hence the answer being $$$2$$$.

On the second example: For the query $$$\{1\,\, 0\}$$$, the shoes won't move, and so their average distance to the door is 2. For the query $$$\{1\,\, 1\}$$$, we can check that the answer is $$$\frac{11}{4} \equiv 750000008 \mod 10^9 + 7$$$. You can easily brute force all possibilites and verify this.