eolymp
bolt
Try our new interface for solving problems
Problems

Combination

Combination

Time limit 1 second
Memory limit 128 MiB

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) (0ji < n) so that C(i, j) is divisible by p. Here

prb7439.gif
prb7439.gif

Input data

The first line contains two integer numbers n, p (1n10^7, 3p100).

Output data

Print the answer.

Examples

Input example #1
5 3

Output example #1
3
Input example #2
100 7
Output example #2
2689
Source 2014 KBTU Open, Spring Kazakhstan, Almaty, April 20, Problem B