## MODBERN - Modular Bernoulli

no tags

Bernoulli numbers are of great interest in mathematics and in computational sciences.
They are rationnal numbers, our interest will be the numerator of the reduced fraction.
Ada Lovelace is sometimes credited as the first programmer ; her interest was on Bernoulli numbers.
You have less than two years before the 200th birthday of Ada, here is a good place to improve your skills.

### Input

The input contains several lines, you don't have to process all, it may be hard, 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 each line you will process, print numerator(BN).
As the answer could not fit in a 64-bit container, just output your answer modulo P, lying in [0...P[.

### Example

```Input:
2 5
5 7
10 13
12 23
[...] some more lines
```
```Output:
1
0
5
22
[...] as many as you can.
```

### Explanation

For the fourth case, B12= (-691)/2730, and (-691) mod 23 = 22.

### Constraints

```1 < N <= 10000
2 < P <= 30000, a prime number
```

Input contains uniform distribution.
The challenge is to be the fastest, constraints allow everybody to get some points.
There are 100000 lines, one point per case.
If you can process all 10^5 lines, your score is 10^6/time.
Have fun ;-)

hide comments

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