Combination
Medium
Execution time limit is 1 second
Runtime memory usage limit is 128 megabytes
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 ≤ j ≤ i < n) so that C(i, j) is divisible by p. Here
Input
The first line contains two integer numbers n, p (1 ≤ n ≤ 10^7, 3 ≤ p ≤ 100).
Output
Print the answer.
Examples
Input #1
Answer #1
Input #2
Answer #2
Submissions 154
Acceptance rate 18%