Problem F
Pascal Magic
Pascal’s Triangle has many fascinating properties. Formally, row $n$ of Pascal’s Triangle contains $n + 1$ entries of the form
\[ {n \choose k} = \frac{n!}{k!(n - k)!}, \quad \text{for } k = 0, 1, \dots , n. \]Your friend has invented a magic trick: given a row number $n$ and a prime number $p$, determine how many entries in the $n$-th row of Pascal’s Triangle are divisible by $p$.
Unfortunately, your friend doesn’t actually know how to perform the trick. Help them by writing a program that computes the answer so they can amaze audiences everywhere!
Input
A single line containing two space-separated integers:
-
$n$ ($0 \le n \le 10^{18}$) — the row of Pascal’s Triangle.
-
$p$ ($p \le 10^{18}$, with $\frac{n}{p} \le 10^6$) — a prime number used for the divisibility check.
Output
Print a single integer — the number of entries in row $n$ of Pascal’s Triangle that are divisible by $p$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 5 |
8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 2 |
7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 3 |
2 |
