题目描述
对于任意十进制正整数$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$取模。
样例输入输出
提示
+ 对 $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$。
样例1说明:1~3中，只有2的最大转换次数为1