On some special occasion Nadia’s company provide very special lunch for all employees of the company. Before the food is served all of the employees must stand in a queue in front of the food counter. The company applied a rule for standing in the queue. For instance if Abul is the supervisor of Babul and Abul stands in kth position from the front of the queue, then Babul cannot stand at any position in between 1 and k-1 from front of the queue. The company has N employees and each of them has one supervisor except one who doesn’t have any supervisor.

You need to calculate in how many ways the queue can be created. You can safely assume that in at least one way the queue can be created.

Input

The first line is the number of test cases.

Each test case:

-         The first line contains 2 integers M and N.

-         Line 2..N: consist of one integer is supervisor of i-employees.

Output

For each test case: the result of this problem module M in one line.

Example

Input:
1
2 2
1
Output:

1

Constraints:
- Number of test cases <= 10 for small data, N <= 100000
- Number of test cases = 1 for large data, N <= 500000
- 1 <= M <= 1000000000
- Time Limit for all tests: 2s