题目描述

给定n个元素，要从中间选择m个元素有多少种方案呢？答案很简单，就是 ${n\choose m}$。如果一个整数$m(0\leq m\leq n)$，${n\choose m}$是某一个质数p的倍数，那么这个m就是讨厌的数字，现在给定了p和n，求有多少个讨厌的数字。

输入格式

第一行是一个正整数$n(1≤n≤10^{100})$。输入的第二行是一个质数 $p(1≤p≤10^7)$。

输出格式

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

6
2

3

提示

30%的数据里，$n≤1000$;

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

题目来源

没有写明来源