PWSUMC - Power Sum

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

Sigma

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]).
As the answer could not fit in a 64-bit 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 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 ;-)


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

hide comments
2014-06-12 22:11:12 abdou_93
your problems are really awesome .
can you tell me a book that you prefer to read it.(thanks Francky)
--ans(Francky)--> I don't have any books, here it's a very common task. (Obviously, I have some maths books from my studies, but I didn't use them specifically in any problem). I don't think my problems are awesome, it's most of them reload of common task. Few of them are 100% genuine, it's true ; eg: HAL9000, MOON2.
@Francky-thanks for reply

Last edit: 2014-06-13 13:20:39
2014-04-26 11:39:36 THE_SCORPION
Any hint to solve it ?
--ans(Francky)--> hint

Last edit: 2014-04-26 15:24:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.