描述

旅行推销员经常花很多时间在旅行中，所以他往往会感到无聊。为了消磨时间，他喜欢对数字执行操作。其中一种操作是取一个正整数 $x$ 并将其减少到其二进制表示中设置为 $1$ 的位数。例如，对于数字 $13$，可以得知 $13_{10} = 1101_{2}$，所以它有 $3$ 个位被设置为 $1$，$13$ 将在一次操作中被减少到 $3$。

他称一个数字为特殊数，如果将其减少到 $1$ 的最小操作数为 $k$。

他想要知道不大于 $n$ 的特殊数有多少个。请帮助旅行推销员，因为他即将到达目的地！

由于答案可能很大，输出结果模 $10^9 + 7$。

输入

第一行包含整数 $n$ ($1 \leq n < 2^{1000}$)。

第二行包含整数 $k$ ($0 \leq k \leq 1000$)。

请注意，$n$ 是在其二进制表示中给出的，没有任何前导零。

输出

输出一个整数 — 不大于 $n$ 的特殊数的数量，模 $10^9 + 7$。

样例

110
2

111111011
2

3

169

注意

在第一个样例中，三个特殊数分别是 $3$，$5$ 和 $6$。它们通过一次操作被减少到 $2$（因为 $3$，$5$ 和 $6$ 中的每个数字都有两个设置位），然后再经过一次操作被减少到 $1$（因为 $2$ 中只有一个设置位）。