题目描述

对于任意十进制正整数$x$，我们定义一次数字转换是将数字$x$转变为$x$在二进制表示下$1$的个数。显然，任意正整数经过若干次数字转换后，最终都会得到$1$，此时经过的转换次数我们也称之为最大转换次数。 例如$(27)_{10}$在二进制下为$(11011)_2$，则$27$经过一次数字转换后，得到了$4$，$4$再经过一次数字转换后得到了$1$。所以$27$经过$2$次转换后，得到了$1$，即$27$的最大转换次数为$2$。 现给定$x$与$k$，请计算出$1$~$x$中，有多少数字的最大转换次数为$k$。

输入格式

输入第一行，一个二进制表示的正整数$x$ 输入第二行，一个非负整数$k$

输出格式

输出$1$~$x$中，最大转换次数为$k$的数字个数，并对$10^9+7$取模。

11
1

1

样例解释 1

1~3中，只有2的最大转换次数为1

11011
2

13

数据范围

• 对 $30\%$ 的数据，$1\leq x \leq 2^{20}$, $0\leq k\leq 5$
• 对 $50\%$ 的数据，$1\leq x \leq 2^{63}-1$, $0\leq k\leq 20$
• 对 $100\%$ 的数据，$1\leq x \leq 2^{1000}$, $0\leq k\leq 10^3$。