旅行推销员花费大量时间旅行,因此他往往会感到无聊。为了打发时间,他喜欢对数字进行运算。一种这样的操作是取一个正整数 x 并将其减少到 x 的二进制表示中设置为 1 的位数。例如,对于数字 13,1310 = 11012 是正确的,因此它设置了 3 位,并且在一次操作中 13 将减少为 3。
如果将一个数字减至 1 的最小运算次数为 k,则他称该数字为特殊数字。
他想找出有多少个不大于n的特殊数字。请帮助旅行推销员,因为他即将到达目的地!
由于答案可能很大,因此输出它对 109 + 7 求模。
输入
第一行包含整数 n (1 ≤ n < 21000)。
第二行包含整数 k (0 ≤ k ≤ 1000)。
请注意,n 以二进制表示形式给出,没有任何前导零。
输出
输出单个整数 — 不大于 n 的特殊数字的数量,以 109 + 7 为模。
示例
输入 #1
110 2
输出 #1
3
输入 #2
111111011 2
输出 #2
169
注意
在第一个示例中,三个特殊数字是 3、5 和 6。它们在一次操作中减少到 2(因为 3、5 和 6 中的每一个都有两个设置位),然后在另一次操作中减少到 1(因为 2 中只有一个设置位)。