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

见题面

见题面