SUMMING - SUMMING

no tags 

Find the sum of $x$ smallest distinct numbers of the series $2^i \times 3^j$ ($i, j \ge 0$).

  • the first number of the series is $1 = 2^0 \times 3^0$
  • the second number of the series is $2 = 2^1 \times 3^0$
  • the third number of the series is $3 = 2^0 \times 3^1$
  • the fourth number of the series is $4 = 2^2 \times 3^0$
  • the fifth number of the series is $6 = 2^1 \times 3^1$

As the sum can be huge print sum modulo $k$.

Input

The input contains 2 numbers $x$ and $k$: $1 \le x \le 10^{14}$, $1 \le k \le 10^8$

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 = 2^0 \times 3^0 + 2^1 \times 3^0 \pmod{1000}$.

Input:
4 1000

Output:
10
Input:
6 2

Output:
0
Input:
16 1000

Output:
300

hide comments
Amit Digga: 2014-11-21 12:44:24

Ok got it... it says smallest numbers..

Amit Digga: 2014-11-18 19:32:22

what is the 6th term???

Amit Digga: 2014-11-18 19:30:35

if 6th is 2^0*3^2 then i/o are wrongly given

abhishek nagpal: 2014-09-04 12:34:03

2590%1000 is 590. Right? -_-

Raghav Jajodia: 2014-09-04 10:58:28

@abhishek nagpal: we need to calculate MOD k also.

abhishek nagpal: 2014-09-04 06:29:26

The answer for x = 16 k 1000, should not be 590?
Sum of first 16 numbers is 2590.

Sumeet Agrawal: 2014-08-06 09:33:26

16 1000 case should give output 333???

M.Suriya krishna: 2014-03-30 10:43:04

Last edit: 2014-03-11 20:15:23

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