题目描述

小明定义了一个函数 $F$：输入的正整数 $x$ 的二进制表达中 $1$ 出现的次数。例如，$F(13)=3$，因为 $(13)_{10} = (1101)_2$。然后，小明发现，$F(x)$ 总是小于等于 $x$，而且任意正整数 $x$ 经过若干次函数 $F$ 的变换后，总会成为 $1$。如果一个正整数 $x$ 恰好经过 $k$ 次函数 $F$ 的变换后成为 $1$，则小明称之为 $k$ 变换数。小明想知道有多少个不大于 $N$ 的 $k$ 变换数，你可以帮帮他吗？

输入格式

第一行表示整数 $N$，是一个没有前导零的二进制表示。第二行包含整数 $k$。

输出格式

输出一个正整数。因为不大于 $N$ 的 $k$ 变换数的数量可能很大，请把结果模 $10^9+7$ 后输出。

样例

输入：

110
2

输出：

3

数据范围

$20\%$ 的数据满足 $1 \le N < 2^{18}$，$0 \le k \le 1000$；$100\%$ 的数据满足 $1 \le N < 2^{1000}$，$0 \le k \le 1000$。