小蓝最近在学习二进制。他想知道111 到NNN 中有多少个数满足其二进制表示中恰好有KKK 个111。你能帮助他吗？
输入格式输入一行包含两个整数NNN 和KKK。
输出格式输出一个整数表示答案。
输入样例 7 2 输出样例 3 数据范围对于30%30\%30% 的评测用例，1≤N≤10 6 1 ≤ N ≤ 10^61≤N≤106,1≤K≤101 ≤ K ≤ 101≤K≤10。 对于60%60\%60% 的评测用例，1≤N≤2×10 9 1 ≤ N ≤ 2 × 10^91≤N≤2×109,1≤K≤301 ≤ K ≤ 301≤K≤30。 对于所有评测用例，1≤N≤10 18 1 ≤ N ≤ 10^{18}1≤N≤1018,1≤K≤501 ≤ K ≤ 501≤K≤50。
算法1(数位DP)非常明显这道题目是典型的数位DP的题目，题干说到在某个区间，求满足某种条件的数的个数，即这道题可以用数位DP过掉，再分析一下时间复杂度，其数据范围在10 18 10^{18}1018上，从这里可以推断出时间复杂度大概率应该控制在O(log(n))O(log(n))O(log(n))，此时数位DP正好可以将此题AC掉！还需注意的一点是此题会爆int，应该用long long。
首先分析一下此题的数位DP的逻辑，如下图所示： 设一个数有nnn 位，数N=a n an − 1an − 2......a 1 a 0 N=a_na_{n-1}a_{n-2}......a_1a_0N=anan−1an−2......a1a0，需要选出KKK 个111。 
先预处理一下组合数，根据递推式：C n k =Cn − 1 k − 1+Cn − 1k C_n^k=C_{n-1}^{k-1}+C_{n-1}^kCnk=Cn−1k−1+Cn−1k 