Zju2116 Christopher

给定 $n$ 个元素，从中选择 $m$ 个元素的方案数为组合数 $\binom{n}{m}$。

对于整数 $m$，其中 $0\le m\le n$，如果 $\binom{n}{m}$ 是质数 $p$ 的倍数，则称 $m$ 为“讨厌的数字”。

给定 $n$ 和质数 $p$，求讨厌的数字的个数。

输入格式

输入共两行。

第一行包含一个正整数 $n$。

第二行包含一个质数 $p$。

输出格式

输出一行一个整数，表示讨厌的数字的个数。

样例输入

6
2

样例输出

3

数据范围

• $1\le n\le 10^{100}$；
• $2\le p\le 10^7$，且 $p$ 为质数；
• 对于 $30\%$ 的数据，$n\le 1000$；
• 对于 $100\%$ 的数据，$n\le 10^{100}$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

6
2

输出

3