Zju2116 Christopher

时间限制:1s      空间限制:64MB

题目描述

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


输入格式

第一行是一个正整数n,(1≤n≤10100)。输入的第二行是一个质数p(1≤p≤107)。


输出格式

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


样例输入

6
2

样例输出

3

提示

30%的数据里,n≤1000; 100%的数据里,n≤10^100


题目来源

没有写明来源