Travelling Salesman and Special Numbers

题意翻译

对于一个正整数x，我们定义一次操作是将其变为它二进制下“1”的个数,比如我们知道$13_{10}$=$1101_2$ ,而1101有三个"1",所以对13进行一次操作就会将其变为3。显而易见的是，对于一个正整数，我们在进行若干次操作后，一定会将其变为1。 给定n和kk，其中n是在二进制下被给出，求出所有不大于n且将其变为1的最小操作次数为kk的数的个数对$10^9+7$取模的结果。

题目描述

The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer $ x $ and reduce it to the number of bits set to $ 1 $ in the binary representation of $ x $ . For example for number $ 13 $ it's true that $ 13_{10}=1101_{2} $ , so it has $ 3 $ bits set and $ 13 $ will be reduced to $ 3 $ in one operation. He calls a number special if the minimum number of operations to reduce it to $ 1 $ is $ k $ . He wants to find out how many special numbers exist which are not greater than $ n $ . Please help the Travelling Salesman, as he is about to reach his destination! Since the answer can be large, output it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<2^{1000} $ ). The second line contains integer $ k $ ( $ 0<=k<=1000 $ ). Note that $ n $ is given in its binary representation without any leading zeros.

输出格式

Output a single integer — the number of special numbers not greater than $ n $ , modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

110
2

输出样例 #1

3

输入样例 #2

111111011
2

输出样例 #2

169

说明

In the first sample, the three special numbers are $ 3 $ , $ 5 $ and $ 6 $ . They get reduced to $ 2 $ in one operation (since there are two set bits in each of $ 3 $ , $ 5 $ and $ 6 $ ) and then to $ 1 $ in one more operation (since there is only one set bit in $ 2 $ ).