304796: CF914C. Travelling Salesman and Special Numbers

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 $ ).

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: