题目描述

如果组合数 $C_n^m(1≤n≤10^{100} , 0≤ m ≤ n)$ 是质数 $p(1≤p≤10^7)$的倍数，那么这个 $m$ 就是讨厌的数字。现在给定了 $p$ 和 $n$，求有多少个讨厌的数字。

输入格式

第一行是一个正整数 $n$ 。 第二行是一个质数 $p$ 。

输出格式

只有一行，表示讨厌的数字的个数。

6
2

3

提示

$30\%$ 的数据里，$n≤1000$ ；

$100\%$ 的数据里，$n≤10^{100}$ 。