Combination#7439

Combination

1 second

128 megabytes

Medium

How many numbers are divisible by the prime number $p$ in the first $n$ rows of Pascal Triangle? In other words, find the number of pairs ( $j$ , $i$ ) ( $0 \leq j \leq i < n$ 0 \le j \le i < n) so that $C (i, j)$ C(i, j) is divisible by $p$ . Here

Input

The first line contains two integer numbers $n$ , $p$ ( $1 \leq n \leq 1 0^{7}$ 1 \le n \le 10^7, $3 \leq p \leq 100$ 3 \le p \le 100).

Output

Print the answer.

Examples

Example 1

Loading

Example 2

Loading

0 \leq j \leq i < n

C (i, j)

1 \leq n \leq 1 0^{7}

3 \leq p \leq 100