Solve the programming task below in a Python markdown code block.
Let us calculate the sum of k-th powers of natural numbers from 1 to n. As the result can be quite large, output the result modulo some integer p.

------ Input ------ 

First t≤10 - the number of test cases.
Each test case consist of numbers: 1≤n≤1000000000, 1≤k≤100, 1≤p≤1000000000.

------ Output ------ 

For each test case, output the value: (1^{k}+2^{k}+...+n^{k}) mod p.

----- Sample Input 1 ------ 
4
10 1 1000000
10 2 1000000
10 3 1000000
10 4 1000000
----- Sample Output 1 ------ 
55
385
3025
25333