SUMMING - SUMMING

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

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.