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