## PWSUMC - Power Sum

no tags

Some people may found PWSUM a too easy problem. We propose here some serious constraints.

### Input

The input contains several lines, you don't have to process all, it may be impossible, only all first ones you are able to, in the given time. Each line contains two integers : N, and P, a prime number.

### Output

For the kth line, print Sum(i^k for i in [1..N]).
The difficulty will seriously increase as you will process lines.

### Example

```Input:
2 5
3 7
2 13
[...] some more lines
```
```Output:
3
0
9
[...] as many as you can.
```

### Explanations

For the first line : 1^1 + 2^1 = 3 (mod[5]).
For the second line : 1^2 + 2^2 + 3^2 = 14 = 0 (mod[7])
For the third line : 1^3 + 2^3 = 9 (mod[13]).

### Constraints

```0 < N <= 10^9
1 < P <= 10^9, a prime number
```

The numbers N are uniform randomly chosen. The prime numbers P are log-uniform randomly chosen.
The challenge is to be the fastest. There are 100000 lines, one point per case.
Constraints allow everybody to get some points.
Have fun ;-)