Xiao Dou likes to play games. Now he is in a situation where each monster has a health value of $a_i$, and all monsters have distinct health values. Xiao Dou has an unlimited supply of the spell "Defile". The effect of "Defile" is to deal 1 damage to all monsters. If any monster dies, the spell is cast again. We consider a monster to be dead if its health value reaches 0.

When Xiao Dou uses one "Defile" spell, he gains a certain number of points, calculated as follows: after using a "Defile" spell, each monster damaged by "Defile" generates $x^k$ points, where $x$ is the health of the monster before taking damage, and $k$ is the number of "Defile" spells required to kill all monsters.

Input

The first line contains an integer $T$ ($T \le 10$), representing the number of test cases. For each test case, the first line contains $n$ and $m$, where $n$ is the maximum health of the current monsters, and $m$ is the number of distinct health values present. The next $m$ lines each contain an integer $a_i$, representing the health of a monster on the field.

Output

For each test case, output one integer on a new line, representing the final score Xiao Dou can obtain. Since this score can be very large, output it modulo $10^9 + 7$.

Examples

Input 1

2
10 1
5
4 2
1
2

Output 1

415
135

Constraints

• For 10% of the data, $m = 0$
• For 20% of the data, $m \le 1$
• For 30% of the data, $m \le 2$
• For 40% of the data, $m \le 3$
• For 50% of the data, $m \le 4$
• For 60% of the data, $m \le 5$
• For 100% of the data, $m \le 50$
• For 100% of the data, $n \le 10^{13}$