Alice has a warehouse with boxes and the box has number . All box numbers are different and range from to . Alice wants to rearrange the boxes in the following way:
You are given triplets . For each of them, Alice asks you to tell how many different sequences of boxes she can get by selecting the following values.
Since these numbers can be very large, you need to subtract the remainder of their division by the prime number .
Note: Two sequences of boxes are considered different if there is a position in which the boxes in both sequences have a different number.
Input format
Output format
Print lines where the line contains the remainder of dividing the number of possible sequences for the triple by .
Constraints
In the first case:
For the first query, result = 2 because it can be swapped 2 and 4.
For the second query, result = 1 because we cannot change any two elements and it turns out that we have only one sequence
For the third query, result = 2 because it can be swapped 2 and 4.
For the fourth query, result = 6 because any two adjacent elements can be swapped.