N.K.P.

3

1 votes
Hard
Problem

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 ≤ N109
1 ≤ K102
1 ≤ P109

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.

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?