Let be a fixed integer.
A permutation is a bijection from the set to itself.
A cycle of length () is a permutation where different integers exist such that and, for all not in , .
The composition of permutations , written , is their composition as functions.
Steve has some cycles . He knows the length of cycle is , but he does not know exactly what the cycles are.
He finds that the composition of the cycles is a cycle of length .
He wants to know how many possibilities of exist.
Input Format
The first line contains , the number of test cases.
Each test case contains the following information:
The first line of each test case contains two space separated integers, and .
The second line of each test case contains integers, .
Constraints
Sum of
Sum of
Output Format
Output lines. Each line contains a single integer, the answer to the corresponding test case.
Since the answers may be very large, output them modulo .
Sample Input
1
3 2
2 2
Sample Output
6
Explanation
There are three cycles of length . The composition of two cycles of length is a cycle of length if, and only if, the two cycles are different. So, there are possibilities.