Processing math: 100%

SUMMING - SUMMING

Find the sum of x smallest distinct numbers of the series 2i×3j (i,j0).

  • the first number of the series is 1=20×30
  • the second number of the series is 2=21×30
  • the third number of the series is 3=20×31
  • the fourth number of the series is 4=22×30
  • the fifth number of the series is 6=21×31

As the sum can be huge print sum modulo k.

Input

The input contains 2 numbers x and k: 1x1014, 1k108

Output

The output contains sum of the first x numbers of the series modulo k.

Example

Input:
1 1000

Output:
1
Input:
2 1000

Output:
3

Explanation: 3=20×30+21×30(mod1000).

Input:
4 1000

Output:
10
Input:
6 2

Output:
0
Input:
16 1000

Output:
300

Added by:priyamehtanit
Date:2013-09-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-11-21 12:44:24 Amit Digga
Ok got it... it says smallest numbers..
2014-11-18 19:32:22 Amit Digga
what is the 6th term???
2014-11-18 19:30:35 Amit Digga
if 6th is 2^0*3^2 then i/o are wrongly given
2014-09-04 12:34:03 abhishek nagpal
2590%1000 is 590. Right? -_-
2014-09-04 10:58:28 Raghav Jajodia
@abhishek nagpal: we need to calculate MOD k also.
2014-09-04 06:29:26 abhishek nagpal
The answer for x = 16 k 1000, should not be 590?
Sum of first 16 numbers is 2590.
2014-08-06 09:33:26 Sumeet Agrawal
16 1000 case should give output 333???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.