M. Resli-utiful Indices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Resli is a contestant, judge, system and administrator. He can do literally everything, but can he come up with good problems? Here is Resli's problem for you.

We define an index $$$i$$$ of some permutation $$$P$$$ to be a Resli-utiful index if it holds that $$$P_i \gt P_{i + 1}$$$.

You will be building a permutation $$$P$$$ of length $$$N$$$. You will be given a set $$$S$$$ of $$$K$$$ distinct integers, that represents some specific indices of permutation $$$P$$$.

You need to count the number of permutations $$$P$$$ of length $$$N$$$, such that for every Resli-utiful index $$$i$$$ of $$$P$$$, it holds that:

  • $$$i$$$ belongs to $$$S$$$. In other words, there exists some index $$$j$$$ such that $$$S_j = i$$$.

Find the answer, and print it modulo $$$10^9 + 7$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains two integers $$$N$$$ and $$$K$$$ $$$(2 \le N \le 2\cdot 10^5$$$, $$$1 \le K \lt N)$$$.

The second line of each testcase contains $$$K$$$ space-separated integers $$$S_1, S_2, \dots, S_K$$$ $$$(1 \le S_i \lt N)$$$ — the specific indices of $$$P$$$.

It's guaranteed that the sum of $$$K$$$ over all testcases does not exceed $$$2\cdot 10^5$$$

Output

For each testcase print a single integer — the number of permutations $$$P$$$ that satisfy the condition, modulo $$$10^9+7$$$.

Example
Input
3
2 1
1
3 2
1 2
3 1
2
Output
2
6
3