Indivisibility of binomial coefficients#638

Indivisibility of binomial coefficients

0.5 seconds
64 megabytes
Easy

Let us denote by C_n^i the binomial coefficient where 0 \leq i \leq n and , are integers. Given a natural number and a prime number , find the number of integers from \{0, 1, \ldots, n\} such that C_n^i is not divisible by .

Input

The input file contains a single line with a natural number (n \leq 10^{18}) and a prime number (p < 10^{18}).

Output

Print the answer in a single line of the output file.

Examples

Example 1

Loading
Loading