Problem: The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer x and reduce it to the number of bits set to 1 in the binary representation of x. For example for number 13 it's true that 1310 = 11012, so it has 3 bits set and 13 will be reduced to 3 in one operation.

He calls a number special if the minimum number of operations to reduce it to 1 is k.

He wants to find out how many special numbers exist which are not greater than n. Please help the Travelling Salesman, as he is about to reach his destination!

Since the answer can be large, output it modulo 109 + 7.

Input

The first line contains integer n (1 ≤ n < 21000).

The second line contains integer k (0 ≤ k ≤ 1000).

Note that n is given in its binary representation without any leading zeros.

Output

Output a single integer — the number of special numbers not greater than n, modulo 109 + 7.

Examples

Input

110
2


Output

3


Input

111111011
2


Output

169

Note

In the first sample, the three special numbers are 3, 5 and 6. They get reduced to 2 in one operation (since there are two set bits in each of 3, 5 and 6) and then to 1 in one more operation (since there is only one set bit in 2).

Solution (in PYTHON):

Solution:
import bisect
import operator as op


ones = [0] * 1001
special_k = [list() for _ in range(6)]
max_k = 5

bi_coeffs = []


def bi_coeff_calc(n):
    global bi_coeffs
    bi_coeffs.append([1])
    bi_coeffs.append([1, 1])
    for _i in xrange(2, n+1):
        _list = [1]
        for _j in xrange(0, _i-1):
            _list.append(bi_coeffs[_i-1][_j]+bi_coeffs[_i-1][_j+1])
        _list.append(1)
        bi_coeffs.append(_list)

    # print bi_coeffs


def ncr(n, r):
    global bi_coeffs
    # print  n,r
    # r = min(r, n-r)
    # if r == 0: return 1
    # numer = reduce(op.mul, xrange(n, n-r, -1)) #% 1000000007
    # denom = reduce(op.mul, xrange(1, r+1)) #% 1000000007
    # return (numer//denom) % 1000000007
    return bi_coeffs[n][r]


def find_ones():
    global ones
    for _i in range(1001):
        n = _i
        w = 0
        while (n):
            w += 1
            n &= n - 1
        ones[_i] = w

110111111100010111001000001110000000100001101100111110010000110011001011001011100101101110001111010110110101001010110000010011110101110100001011000001110110011101000100001101101100101000000011110100000000111000101000111000011100001100100111011011000010000110010011100000011100100100000000110110101101011100010001111010000010001110001111011011001011010001101100101010110101101100010001011101110000010101100111011010001011001101011110010111010001001010100110110011110110010000010010010100000111101001010111010000111011111110001011100100000111000000010000110110011111001000011001100101100101110010110111000111101011011010100101011000001001111010111010000101100000111011001110100010000110110110010100000001111010000000011100010100011100001110000110010011101101100001000011001001110000001110010010000000011011010110101110001000111101000001000111000111101101100101101000110110010101011010110110001000101110111000001010110011101101000101100110101111001011101000100101010011011001111011001000001001001010000
def find_special(n):
    k = 1

    while n != 1:
        n = ones[n]
        k += 1
        if k >= 9:
            break

    return k


def find_specials():
    global ones, special_k

    for _i in range(1, 1001):
        special_k[find_special(_i)].append(_i)


if __name__ == "__main__":
    # bi_coeff_calc(5)
    # exit(0)
    n, k = raw_input(), int(raw_input())
    find_ones()
    find_specials()

    # n = '111111011'
    # k = 2
    size_n = len(n)
    count_ones_n = n.count("1")

    if k > 5:
        print 0
        exit(0)
    elif k == 0:
        print 1
        exit(0)
    elif k == 1:
        print size_n-1
        exit(0)

    interest_list = special_k[k]
    bi_coeff_calc(size_n)

    result = 0
    no_ones_till_now = 0
    for index, item in enumerate(n):
        if item == '0': continue
        right_chars = size_n - index - 1

        fit_index = bisect.bisect_left(interest_list, no_ones_till_now)
        # iters = 0
        for _interest_item_index in xrange(fit_index, len(interest_list)):
            # if _interest_item-no_ones_till_now < 0: continue
            _interest_item = interest_list[_interest_item_index]
            if _interest_item-no_ones_till_now <= right_chars:
                # print right_chars, _interest_item-no_ones_till_now, no_ones_till_now
                result += ncr(right_chars, _interest_item-no_ones_till_now)
                result %= 1000000007
            else:
                break
            # iters += 1
        # print iters

        # for _j in range(right_chars, -1, -1):
        #     if _j+no_ones_till_now in interest_list:
        #         # print right_chars, _j, no_ones_till_now
        #         result += ncr(right_chars, _j)
        #         result %= 1000000007
        no_ones_till_now += 1

    if no_ones_till_now in interest_list:
        result += 1
        result %= 1000000007
    print result