Bajtazar has bought a huge chandelier for his spacious living room. As is often the case with furniture bought in a store, it must be assembled from the provided parts. The set of chandelier parts consists of an infinite number of light bulb sockets, numbered with consecutive integers starting from 1, and an infinite number of connectors that can be used to connect two sockets.

Each socket is of one of $k$ types, and the number $k$ is odd due to the manufacturer's preferences. The sockets, in order of their numbering, are of types $1, 2, \dots, k, 1, 2, \dots, k, 1, 2, \dots, k, \dots$. Each socket of type $t$ has one handle on top, through which it can be connected to a socket located above it, and exactly $t$ handles on the bottom, through which it can be connected to sockets located below it. The handle on top of socket number 1, instead of being connected to another socket, will be used to attach the entire chandelier to the ceiling.

Now, Bajtazar must assemble his chandelier. For each subsequent socket starting from 1, he follows the rule from the manual: Take the next socket and connect each of its bottom handles to the top handle of the socket with the smallest number that is not yet connected to any other socket. For example, for $k = 3$, socket 1 is of type 1, so we connect it to socket 2. Socket 2 is of type 2, so we connect it to sockets 3 and 4. Socket 3 is of type 3, so we connect it to sockets 5, 6, and 7. Socket 4 is of type 1, so we connect it only to socket 8, and so on. See the figure below.

Bajtazar does not want to assemble his chandelier infinitely, so he will settle for only a part of it. He considers $q$ possible scenarios.

In the $i$-th scenario, Bajtazar will assemble the chandelier from all sockets that are at a distance of at most $p_i$ from the ceiling. The distance from the ceiling is defined in a natural way: socket 1 is at distance 1, and if socket $x$ is connected for the first time to socket $y$, then the distance of socket $x$ is one greater than the distance of socket $y$. In the example above, socket 1 is at distance 1, socket 2 is at distance 2, sockets 3 and 4 are at distance 3, and sockets 5, 6, 7, and 8 are at distance 4.

The description of the $i$-th scenario also includes a sequence $d_i$ of numbers $a_{i,j}$. They mean that Bajtazar wonders how many sequences $b_{i,j}$ containing $d_i$ distinct socket numbers exist such that for every $j$ ($1 \le j \le d_i$), socket $b_{i,j}$ is of type $a_{i,j}$, and for every $j$ ($1 \le j < d_i$), socket $b_{i,j}$ is connected to socket $b_{i,j+1}$. Since this number can be very large, it is sufficient to provide its remainder when divided by $10^9 + 7$. Your task is to provide this number for each scenario considered by Bajtazar.

Input

The first line of input contains two integers $k$ and $q$ ($1 \le k < 10^7$, $k$ is odd, $1 \le q \le 200\,000$), representing the number of socket types and the number of scenarios considered by Bajtazar.

The next $2q$ lines contain the descriptions of $q$ scenarios; the $i$-th of them contains two lines. The first line contains two integers $d_i$ and $p_i$ ($1 \le d_i \le 10^6$, $1 \le p_i \le 10^9$), representing the length of the sequence and the distance limit from the ceiling. The second line contains a sequence of $d_i$ integers, where the $j$-th of them is $a_{i,j}$ ($1 \le a_{i,j} \le k$).

Let $S$ denote the sum of the numbers $d_i$. It holds that $S \le 10^6$.

Output

Your program should output $q$ lines containing the answers for the consecutive scenarios of Bajtazar.

Examples

Input 1

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

Output 1

2
2
0
6

Note

In the first scenario, there are exactly two sequences of socket numbers: 3, 2, 1 and 3, 2, 4. In the second scenario, there are also exactly two sequences of socket numbers: 5, 3, 2 and 2, 3, 5. Note that sequences 5, 3, 5 and 2, 3, 2 should not be included because the socket numbers in these sequences repeat. In the third scenario, among the sockets at a distance of at most 4 from the ceiling, there is no sequence of sockets whose types are 3, 1, 2 in order. In the fourth scenario, we ask for the number of type 1 sockets at a distance of at most 5 from the ceiling; there are 6 of them.

Subtasks

In each subtask, there are test groups satisfying $d_i = 1$ for each $i$, which are worth 50% of the points for that subtask.