P4593 [TJOI2018] Textbook Defile

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.

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 $T$ lines. The $i$-th line contains the final score Xiao Dou can obtain in the $i$-th test case, modulo $10^9+7$.

- 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