You are given the equation and a positive integer, . Calculate . There are test cases.
Input Format
The first line contains , the number of test cases.
The next lines contain three space separated integers: and , respectively.
Constraints
Output Format
If the result is defined, it is always a rational number. However, it can be very big.
Output the answer modulo .
If the answer is and is not divisible by , there is a unique integer where .
Output this integer, .
It is guaranteed that is not divisible by for all test cases.
Sample Input
2
2 1 2
5 6 7
Sample Output
666666670
237627959
Explanation
If then and
.
So, the answer is .