J. More Banknote
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Neuro-sama has a single banknote with a value of $$$n$$$ dollars. She can repeatedly apply the following operation:

  • Take a banknote with a value $$$t$$$ such that $$$t \ge k$$$, and replace it with $$$k+1$$$ new banknotes: $$$k$$$ banknotes each with value $$$\lfloor t/k \rfloor$$$, and one banknote with value $$$t \bmod k$$$.

Neuro keeps applying this operation until all banknotes have a value less than $$$k$$$. Now she is interested in the number of $$$0$$$-dollar banknotes that she will have at the end. As Neuro-sama's fan, please find the answer for her.

You will be given $$$q$$$ independent queries. For each query, output the number of $$$0$$$-dollar banknotes obtained at the end, modulo $$$10^9+7$$$.

Input

The first line contains an integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^{5}$$$) — the number of queries.

Then $$$2q$$$ lines follow, describing the queries:

  • The first line of each query contains two integers $$$k$$$ and $$$m$$$ ($$$2 \le k \le 42$$$, $$$1 \le m \le 2 \cdot 10^{5}$$$).
  • The second line of each query contains $$$m$$$ space-separated integers $$$a_{m-1}, a_{m-2}, \dots, a_0$$$ ($$$0 \le a_i \lt k$$$), representing the number $$$n$$$ in base $$$k$$$: $$$n = a_{m-1} k^{\,m-1} + a_{m-2} k^{\,m-2} + \dots + a_1 k + a_0$$$.

The total number of integers $$$m$$$ across all queries satisfies $$$1\le \sum m \le 2\cdot 10^5$$$.

Output

For each query, output a single integer — the answer modulo $$$10^9+7$$$.

Example
Input
1
3 10
1 2 1 0 0 2 1 2 1 2
Output
972
Note

In this problem, $$$a$$$ modulo $$$p$$$ refers to taking the remainder of $$$a$$$ after division by $$$p$$$. For example:

  • $$$11$$$ modulo $$$5 = 1$$$ ($$$11 = 5\times 2 + 1$$$);
  • $$$7$$$ modulo $$$5 = 2$$$ ($$$7 = 5\times 1 + 2$$$);
  • $$$3$$$ modulo $$$5 = 3$$$ ($$$3$$$ is already smaller than $$$5$$$).