Once the famous Sir NKP went to give a speech in Oxford University . During the Question hour , one Student in the hall raised a question to find
The sum of Kth powers of first N natural numbers modulus some Natural Number P.
It was a geeky ONE ! but Sir NKP smiled and wrote the algorithm to compute the above asked problem ! Unfortunately the paper in which he wrote the solution went missing due to that irresponsible student !
Can you Devise a code for the student ?
CONSTRAINTS:
1 ≤ T ≤ 10
1 ≤ N ≤ 109
1 ≤ K ≤ 102
1 ≤ P ≤ 109
INPUT:
First line of input contains T , the number of test cases . Each test case contains three space separated integers N,K,P.
OUTPUT:
For each test case output the value (1K+2K+...+NK) mod P in a single line.