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

输入描述

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

输出描述

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

输入样例

110
2

输出样例

3

数据规模

• 20%的数据满足1 ≤ N < 2¹⁸，0 ≤ k ≤ 1000；
• 100%的数据满足1 ≤ N < 2¹⁰⁰⁰，0 ≤ k ≤ 1000。