PWSUMC  Power Sum
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 k^{th} line, print Sum(i^k for i in [1..N]).
As the answer could not fit in a 64bit container, just output your answer modulo P.
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 loguniform 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 ;)
hide comments
abdou_93:
20140612 22:11:12
your problems are really awesome .


THE_SCORPION:
20140426 11:39:36
Any hint to solve it ?

Added by:  Francky 
Date:  20140323 
Time limit:  25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 