## AFSK - Power Factor Sum Sum (hard)

no tags

Here is a mixed edition of Divisor Summation Powered and Amazing Factor Sequence (medium).

### The powered factor sequence

For k an integer number, we define our powered factor sequence with:

ak[0] = 0; ak[1] = 1, and

for n > 1, ak[n] = ak[n - 1] + sum({x^k | 0 < x ≤ n and n % x = 0}).

### Input

First line of input contains an integer T, the number of test cases.

Each of the next T lines contains three integers n, k, m.

### Output

For each test case, print ak[n] on a single line.
As the answer could be a big number, you just have to output it modulo m.

### Example

```Input:
3
3 1 10
4 2 55
5 3 97```
```Output:
8
37
43```

### Constraints

```0 < T < 101
0 < n < 10^9
0 < k < 11
1 < m < 10^17
```

Numbers n, k, m are uniform-randomly chosen.
For your information, there's two input files, the first one is 'easy' with n≤100.
My (1kB)-python code get AC around 0.96s. I have a much slower basic PIKE AC (4.8s).
(Edit 2017-02-11 ; timings and TL updated after compiler changes)