C. Kaosar loves Polynomials
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$k$$$, $$$n$$$ and a polynomial $$$P(x) = a_0+a_1x+a_2x^2+....+a_nx^n$$$.

Note

  • $$$P^{1}(x) = P(x)$$$

  • $$$P^{2}(x) = P(x)\cdot P(x)$$$

  • $$$P^{3}(x)=P(x) \cdot P(x) \cdot P(x)$$$
  • ...

  • $$$P^i(x) = \underbrace{P(x) \cdot P(x) \cdot \dots \cdot P(x)}_{\text{i times}}$$$

Your task is to find the value of total sum of the coefficients of $$$P^k(x)$$$ modulo $$$(10^9 + 7)$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$. The description of the test cases follows.

The first line of each test case contains $$$2$$$ integers $$$k$$$ $$$(1 \leq k \leq 2 \cdot 10^5)$$$ and $$$n$$$ $$$(0 \leq n \leq 2 \cdot 10^5)$$$.

The next line will contain $$$n+1$$$ integers $$$a_0,a_1,...,a_n$$$ $$$(-10^{9} \leq a_i \leq 10^{9})$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$. However, there is no limit to the sum of $$$k$$$.

Output

For each test case, print the sum modulo $$$(10^9 + 7)$$$.

Example
Input
4
1 1
1 1
2 1
5 3
2 1
-2 -2
2003 3
-1 4 -2 1
Output
2
64
16
993748093
Note

In the first test, $$$P(x) = 1+x$$$. The sum of its coefficients is $$$1+1 = 2.$$$

In the second test, $$$P(x) = 5+3x$$$. We can get $$$P^{2}(x) = P(x) \cdot P(x) = 25+30x+9x^2$$$. The sum of its coefficients is $$$25+30+9 = 64$$$.