Description

Xiao Dou likes playing games. He is now facing a situation in a game where each monster has health $a_i$, and all monsters have distinct health values. Xiao Dou has an unlimited number of "Defile" cards. 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 when its health reaches $0$.

Each time Xiao Dou uses one "Defile," he gets some score. The score is calculated as follows: after using a single "Defile," every monster that is damaged by "Defile" grants Xiao Dou $x^k$ points, where $x$ is that monster’s health value before the damage is applied, and $k$ is the number of "Defile" cards needed to kill all monsters. Note: automatic re-casts of "Defile" caused by monster deaths do not count toward $k$, and they do not increase Xiao Dou’s score.

Input Format

The first line contains an integer $T$ ($T \le 10$), the number of test cases.

For each test case, the first line contains $n$, $m$, where $n$ is the maximum health value among the monsters, and $m$ is the number of health values that are missing.

The next $m$ lines each contain one number $a_i$, indicating that there is no monster with health $a_i$ on the field.

Output Format

Output $T$ lines. The $i$-th line contains the final score Xiao Dou can obtain in the $i$-th test case, modulo $10^9+7$.

2
10 1
5
4 2
1
2

415
135

Hint

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

Translated by ChatGPT 5