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 13_10 = 1101_2, 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 10^9 + 7.


-----Input-----

The first line contains integer n (1 ≤ n < 2^1000).

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 10^9 + 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).

Difficulty: competition

Starter code:

Solutions:
mas = [[] for i in range(1001)]
mas[0].append(1)
mas[0].append(1)
for i in range(1, 1000):
    mas[i].append(1)
    for j in range(1, i):
        mas[i].append((mas[i - 1][j] + mas[i - 1][j - 1]) % (10 ** 9 + 7))
    mas[i].append(1)


def c(k, n):
    if k > n:
        return 0
    if k < 0:
        return 0
    nonlocal mas
    return mas[n][k]


m = [0] * 1000
for i in range(1, 1000):
    nw = i
    t = 0
    while nw != 1:
        nw = sum([int(j) for j in str(bin(nw)[2:])])
        t += 1
    m[i] = t
m[1] = 0
n = input()
k = int(input())
if k >= 6:
    print(0)
    return
if k == 0:
    print(1)
    return
if k == 1:
    print(len(n) - 1)
    return
ans = 0
for kkk in range(1, 1000):
    if m[kkk] == k - 1:
        nw = kkk
        t = 0
        for i in range(len(n)):
            if n[i] == '1':
                ans += c(nw - t, len(n) - 1 - i)
                ans %= 10 ** 9 + 7
                t += 1
        if sum([int(j) for j in n]) == kkk:
            ans += 1
            ans %= 10 ** 9 + 7


print(ans)


# int(input())
# [int(i) for i in input().split()]

def count_oper(x):
    if x == 1: return(0)

    res = 0
    y = x
    while y > 0:
        if y % 2 == 1: res += 1
        y = y//2

    return(count_oper(res) + 1)

def solve(s,k):
    
    a = []
    ones = []
    for i in range(len(s)):
        c= s[i]
        a.append(int(c == '1'))
        if c == '1': ones.append(i)

    nones = len(ones)
    n = len(a)

    
    if k == 0 :
        print(1)
        return
    
    if k == 1 and n != 1:
        print(n-1)
        return
    
    if n == 1:
        if k > 0: print(0)
        else: print(1)
        return

        #print("main")
    # compute binomial coeff-s:
    c = []
    c.append([0]*(n+1))
    for n1 in range(1,n+1):
        tmp = [0]*(n+1)
        for m in range(n1+1):
            #print(n1,m)
            if m == 0 or m == n1: tmp[m] = 1
            else:
                tmp[m] = (c[n1-1][m-1] + c[n1-1][m]) % modulo
        c.append(tmp)

    ans = 0    
    for m in range(1,n+1): # how many 1's should be in a special number?
        if count_oper(m) == k-1: # m ones!
            for j in range(min(nones,m)): # loop over 1's and add corrsponding bin coef
              #  print(j, ones[j])
                ans += (c[n - ones[j] - 1][m - j  ]) % modulo
            if nones >= m: ans += 1

    print(ans % modulo)

s = input()
k = int(input())

modulo = 10**9 + 7

solve(s,k)





from math import factorial
from functools import lru_cache

mod = 1000000007

def num_iters(x):
    ans = 0
    while x > 1:
        x = bin(x).count('1')
        ans += 1
    return ans

@lru_cache(maxsize=1001)
def fact(n):
    return factorial(n) % mod

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

@lru_cache(maxsize=1001)
def inv(a):
    return modinv(a, mod)

def binom(n, k):
    return (fact(n) * inv(fact(k)) * inv(fact(n - k))) % mod

def num_numbers(n, i):
    # number of numbers in [1..n] that have exactly i 1s
    # in their binary representation
    # n is a str

    ans = 0
    num_ones_in_prefix = 0
    for j in range(len(n) - 1):
        pos_right = len(n) - j - 1
        if num_ones_in_prefix + pos_right < i or num_ones_in_prefix > i:
            break
        if n[j] == '1':
            ans = (ans + binom(pos_right, i - num_ones_in_prefix)) % mod
            num_ones_in_prefix += 1

    cnt1 = n.count('1')
    if (n[-1] == '0' and cnt1 == i) or (n[-1] == '1' and cnt1 in (i, i + 1)):
        ans = (ans + 1) % mod

    return ans

precalc = [num_iters(x) for x in range(1001)]

def solve(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return len(n) - 1
    else:
        ans = 0
        for i in range(1, 1001):
            if precalc[i] == k - 1:
                ans = (ans + num_numbers(n, i)) % mod
        return ans

n = input()
k = int(input())

print(solve(n, k))





def reduce(n):
    n=bin(n)[2:]
    n=list(n)
    n=list(map(int,n))
    return sum(n)

def a(n,bits,dp):
    if(bits==0):
        return 1
    
    if(n=='0' or n==''):
        return 0
    if(bits>len(n)):
        return 0
    if(bits==len(n)):
        if(n=='1'*len(n)):
            #print(n,bits,1)
            return 1
        else:
            return 0
    """
    i=1
    while(i<len(n) and n[i]=='0'):
        i+=1
    
    x=dp[len(n)-1][bits] + a(n[i:],bits-1,dp)
    #print(n,bits,dp[len(n)-1][bits],x)
    return x%1000000007
    """
    ans=0
    while(bits!=0 and (n!='' and n!='0') and bits<len(n)):
        ans+=dp[len(n)-1][bits]
        i=1
        while(i<len(n) and n[i]=='0'):
            i+=1
        n=n[i:]
        bits-=1
    if(bits==0):
        ans+=1
    elif(bits==len(n) and n=='1'*len(n)):
        ans+=1
    return ans
        





n=(input())
k=int(input())


if(k>5):
    print(0)
elif(k==0):
    print(1)
elif(k==1):
    print(len(n)-1)

else:
    dp=[]
    dp.append([0,])
    for i in range(1,1002):
        dp.append([])
        
        for j in range(i):
            if(j==0):
                dp[i].append(1)
            else:
                dp[i].append((dp[i-1][j-1]+dp[i-1][j])%1000000007)
        dp[i].append(1)
    
    
    
    
    pos=[]
    for i in range(1,len(n)+1):
        count=0
        I=i
        while(i!=1):
            i=reduce(i)
            count+=1
        if(count==k-1):
            pos.append(I)
    ans=0
    for i in pos:
        ans+=a(n,i,dp)
    #print(dp)
    #print(a('10000',3,dp))
    
    #print(pos)
    print(ans%1000000007)
    


MX = 1030
M = 1000 * 1000 * 1000 + 7
c = [[0] * MX for i in range(MX)]
for i in range(MX):
    c[i][0] = 1
for i in range(1, MX):
    for j in range(1, MX):
        c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
        c[i][j] %= M

num = list(map(int, list(input())))
cnt = int(input())
dp = [0] * MX
for i in range(2, MX):
    dp[i] = dp[bin(i).count('1')] + 1

if cnt == 0:
    print(1)
    return

res = 0

for i in range(1, MX):
    if dp[i] != cnt - 1: continue
    n = len(num) - 1
    k = i
    for pos in range(len(num)):
        if num[pos] == 1:
            # print(n, k)
            #if we put 0 here
            res += c[n][k]
            res %= M
            k -= 1
        n -= 1  
    # print(k)   
    if n == -1 and k == 0:
        res += 1
if cnt == 1: res -= 1
print(res)

n = input()
k = int(input())
MOD = int(1e9 + 7)


a = {0: 0, 1: 0, 2: 1}
for i in range(3, 1001):
    s = bin(i)[2:]
    ones_count = 0
    for x in s:
        if x == "1":
            ones_count += 1
    a[i] = a[ones_count] + 1

answer = 0

table = {}


def bin_coeff(N, K):
    if K > N:
        raise Exception
    if K > N // 2:
        K = N - K
    if K == 0:
        table[(N, 0)] = 1
        return 1
    if (N, K) not in table:
        table[(N, K)] = (N * bin_coeff(N - 1, K - 1) // K)
    return table[(N, K)]


ones = 0
for i, x in enumerate(n):
    if x == "1":
        good = []
        N = len(n) - i - 1
        min = 0 if i > 0 else 1
        for j in range(min, N + 1):
            if a[j + ones] == k - 1:
                good.append(j)
        for x in good:
            answer = (answer + bin_coeff(N, x)) % MOD
            if i == 0 and x == 1:
                answer -= 1
        ones += 1

if a[ones] == k - 1:
    answer += 1

if k == 0:
    answer = 1

if k == 1:
    answer = len(n) - 1


answer = int(answer)
print(answer)


s = input()
k = int(input())
n = len(s)

if k == 0:
    print(1)
    return
if k == 1:
    print(n-1)
    return

st = [0, 0]
for i in range(2, 1000):
    c = 0
    for j in range(10):
        if 1 << j & i:
            c += 1
    st.append(st[c] + 1)

nums = [i for i in range(len(st)) if st[i] == k-1 and i <= n]
if len(nums) == 0:
    print(0)
    return
max_k = nums[-1]

c = [[0 for i in range(max_k+1)] for j in range(n+1)]
c[0][0] = 0
for i in range(n+1):
    c[i][0] = 0
for i in range(max_k+1):
    c[0][i] = 0
for i in range(1, n+1):
    c[i][1] = i
for i in range(2, n+1):
    for j in range(2, min(i+1, max_k+1)):
        c[i][j] = c[i-1][j-1] + c[i-1][j]
        c[i][j] %= 10**9 + 7

ans = 0
for num in nums:
    cnt = num
    for i in range(n):
        if s[i] == '1':
            ans += c[n-i-1][cnt]
            ans %= 10**9 + 7
            cnt -= 1
        if cnt == 0:
            ans += 1
            break
print(ans % (10**9 + 7))

def fact(n):
    if(n==0):
        return 1;
    return(n*fact(n-1))
mod=1000000007
ncrtable=[[0 for i in range(1001)] for j in range(1001)];
ncrtable[0][0]=1;
for row in range(1,1001):
    for col in range(row+1):
        if(col==0):
            ncrtable[row][col]=1;
        else:
            ncrtable[row][col]=ncrtable[row-1][col]+ncrtable[row-1][col-1];
        
def ncr(n,r):
    if(n<r):
        return 0;
    if(r<0):
        return 0;
    return ncrtable[n][r];
def compute(n,x):
    tot=0;
    #cnt=0;
    y=x;
    for i in range(1000,-1,-1):
        if(1<<i & n):
            tot+=ncr(i,x)%mod;
            tot%=mod
            x-=1;
            #cnt+=1;
    if(x==0):
        return((tot+1)%mod);
    return(tot%mod);
arr=[0 for i in range(1002)];
arr[1]=1;
for i in range(2,1001):
    ct=0
    for j in range(32,-1,-1):
        if(1<<j & i):
            ct+=1;
    arr[i]=arr[ct]+1
n=int(input(),2);
#print(n);
   
k=int(input())
ans=0
for i in range(0,1001):
    if(arr[i]==k):
        ans=compute(n,i)+ans;
        ans%=mod;
if(k==1):
    ans-=1;

print(ans);
return
if(n>=1001):
    for i in range(0,1001):
        if(arr[i]==k-1):
            ans=compute(n,i)+ans;
            #ans-=1;
            ans%=mod;
#for i in range(1,1001):
 ##  for j in range(32):
   #     if(1<<j &i):
    #        c+=1;
   # if(c==k-1):
    #    ans+=(mod-1);
     #   ans%=mod;
    
if(k!=1):        
    print(ans);
else:
    print((ans-1));


def Numb(a,k):
    if a == 0:
        return 0
    m = len(bin(a))-3
    if m + 1 < k:
        return 0
    if k == 1:
        return m+1
    if m + 1 == k:
        return Numb(a & ((1<<m)-1), k-1)
    return C[m][k]+Numb(a & ((1<<m)-1), k-1)

s = input()
nDec = int(s,2)
n = len(s)
k = int(input())

C = [[1],[1,1]]
for i in range(n):
    tmp = [1]
    for j in range(1,i+2):
        tmp.append(C[-1][j-1]+C[-1][j])
    tmp.append(1)
    C.append(tmp)

if k == 0:
    print(1)
else:
    NumOfOp = [0 for i in range(n+1)]
    for i in range(2,n+1):
        NumOfOp[i] = NumOfOp[bin(i).count('1')] + 1
    res = 0
    for i in range(1,n+1):
        if NumOfOp[i] == k-1:
            res += Numb(nDec,i)
    if k == 1:
        res -= 1
    print(res%(10**9+7))

mod = 10**9 + 7

def solve(n: str, k: int):
    out = 0
    if k == 0:
        out = 1
    elif k == 1:
        out = len(n)-1
    elif k == 2:
        for i in range(1, min(len(n), 10)):
            x = 2**i
            cnt = 0
            for j in range(len(n)):
                if n[j] == '1':
                    out += C(len(n)-j-1, x-cnt)
                    out %= mod
                    cnt += 1
            if n.count('1') == x:
                out += 1
    elif 3 <= k <= 5:
        d = dict()
        cnt = 0
        for i in range(len(n)):
            if n[i] == '1':
                m = 1
                for j in range(len(n)-i):
                    assertadd(d, j+cnt, m)
                    m *= len(n)-i-j-1
                    m //= j+1
                cnt += 1
        assertadd(d, n.count('1'), 1)
        for key in d:
            out += d[key] * recur(key, k-1)
        out %= mod
    elif k >= 6:
        out = 0
    return out


def assertadd(d: dict, k, v):
    try:
        d[k] += v
    except :
        d[k] = v


def recur(k, level):
    for i in range(level):
        k = bin(k)[2:].count('1')
        if k == 1 and i != level-1:
            return 0
    return 1 if k==1 else 0


def C(n, k):
    if k < 0 or k > n:
        return 0
    out = 1
    for i in range(k):
        out *= n-i
        out //= i+1
    return out % mod


def __starting_point():
    n = input()
    k = int(input())
    print(solve(n, k))


__starting_point()

def main():
    s, k = input(), int(input())
    n = len(s)
    if k < 2:
        print((1, n - 1)[k])
        return
    tais = [n - i - 1 for i, c in enumerate(s) if c == '1']
    tlen, cache, res = len(tais), {(0, 0): 1}, 0

    def c(n, m):
        if 0 <= m <= n:
            if (n, m) not in cache:
                cache[n, m] = (c(n - 1, m - 1) + c(n - 1, m)) % 1000000007
            return cache[n, m]
        return 0

    for m in range(n, 0, -1):
        x, t = m, k
        while x != 1:
            y = 0
            t -= 1
            while x:
                y += x & 1
                x //= 2
            x = y
        if t == 1:
            if len(tais) > m:
                del tais[m:]
            res += sum(c(t, m - i) for i, t in enumerate(tais)) + (m <= tlen)
    print(res % 1000000007)


def __starting_point():
    from sys import setrecursionlimit
    setrecursionlimit(1050)
    main()

__starting_point()

def main():
    s, k = input(), int(input())
    n = len(s)
    if k < 2:
        print((1, n - 1)[k])
        return
    tais = [n - i - 1 for i, c in enumerate(s) if c == '1']
    tlen, cache, res = len(tais), {(0, 0): 1}, 0

    def c(n, m):
        if n < m * 2:
            m = n - m
        if 0 <= m:
            if (n, m) not in cache:
                cache[n, m] = (c(n - 1, m - 1) + c(n - 1, m)) % 1000000007
            return cache[n, m]
        return 0

    for m in range(n, 0, -1):
        x, t = m, k
        while x != 1:
            y = 0
            t -= 1
            while x:
                y += x & 1
                x //= 2
            x = y
        if t == 1:
            if len(tais) > m:
                del tais[m:]
            res += sum(c(t, m - i) for i, t in enumerate(tais)) + (m <= tlen)
    print(res % 1000000007)


def __starting_point():
    from sys import setrecursionlimit

    setrecursionlimit(1050)
    main()

__starting_point()

def main():
    s, k = input(), int(input())
    n = len(s)
    if k < 2:
        print((1, n - 1)[k])
        return
    tais = [n - i - 1 for i, c in enumerate(s) if c == '1']
    tlen, cache, res = len(tais), {}, 0

    def c(n, m):
        if n < m * 2:
            m = n - m
        if 0 < m:
            if (n, m) not in cache:
                cache[n, m] = (c(n - 1, m - 1) + c(n - 1, m)) % 1000000007
            return cache[n, m]
        return not m

    for m in range(n, 0, -1):
        x, t = m, k
        while x != 1:
            y = 0
            t -= 1
            while x:
                y += x & 1
                x //= 2
            x = y
        if t == 1:
            if len(tais) > m:
                del tais[m:]
            res += sum(c(t, m - i) for i, t in enumerate(tais)) + (m <= tlen)
    print(res % 1000000007)


def __starting_point():
    from sys import setrecursionlimit

    setrecursionlimit(1050)
    main()

__starting_point()

def main():
    s, k = input(), int(input())
    n = len(s)
    if k < 2:
        print((1, n - 1)[k])
        return
    tais = [n - i - 1 for i, c in enumerate(s) if c == '1']
    tlen, mod, res = len(tais), 1000000007, 0
    fac, ifac, f = [1], [1], 1
    for i in range(1, n + 1):
        f = f * i % mod
        fac.append(f)
        x = v = 0
        y = u = 1
        a, b = f, mod
        while a:
            q, r = divmod(b, a)
            a, b, x, y, u, v = r, a, u, v, x - u * q, y - v * q
        ifac.append(x)

    def c(n, m):
        return fac[n] * ifac[m] * ifac[n - m] % mod if 0 <= m <= n else 0

    for m in range(n, 0, -1):
        x, t = m, k
        while x != 1:
            y = 0
            t -= 1
            while x:
                y += x & 1
                x //= 2
            x = y
        if t == 1:
            if len(tais) > m:
                del tais[m:]
            res += sum(c(t, m - i) for i, t in enumerate(tais)) + (m <= tlen)
    print(res % mod)


def __starting_point():
    main()

__starting_point()

# python3
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

MOD = int(1e+9 + 7)


def inv(val): return pow(val, MOD - 2, MOD)


@lru_cache(maxsize=None)
def factorial(n):
    return 1 if n < 2 else (factorial(n - 1) * n % MOD)


def choose(n, k):
    return factorial(n) * inv(factorial(k) * factorial(n-k)) % MOD


def numbers_with_bits(length, n):
    nxt = 0
    res = 0
    while nxt != -1 and length > 0:
        top = len(n) - 1 - nxt

        if(length <= top):
            res += choose(top, length)
            res %= MOD

        nxt = n.find('1', nxt + 1)
        length -= 1

    if length == 0:
        res += 1

    return res


def bits(n): return bin(n).count('1')


def solve(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return len(n) - 1  # exclude the 1
    elif k > 5:
        return 0

    ans = 0
    f = [-1, 0]
    for i in range(2, 1001):
        f.append(f[bits(i)] + 1)
        if f[i] == k - 1:
            ans += numbers_with_bits(i, n)
            ans %= MOD
    return ans

print(solve(n=input(), k=int(input())))


# -*- encoding:utf-8 -*-

import sys
from functools import reduce

#sys.stdin = open('C.in', 'r')
def debug(*args):
    return
    print('debug ',end='')
    for x in args:
        print(x,end=' ')
    print('')

n = input()
k = int(input())
mod = 1000000007
#n = '1'*1000
#k = 5

a = [0] * 1001

def bitnum(x):
    ans = 0
    while x:
        if x & 1: ans += 1
        x >>= 1
    return ans

for i in range(1,1001):
    bn = bitnum(i)
    a[i] = a[bn] + 1

#debug([i for i in range(10)])
#debug(a[:10])

''' number of bits that needs k operations to reduce to 1 '''
a = [i for i in range(len(a)) if a[i]==k]
a = list(filter(lambda x: x <= len(n), a))
#debug(a[:10])

C = [None for i in range(1001)]
C[0] = [1, 0]
for i in range(1, len(C)):
    C[i] = [1] + [(C[i-1][j]+C[i-1][j-1])%mod for j in range(1,i)] + [1]

answer = 0

def cal2(x, arr):
    nonlocal answer
    while True:
        ln = len(arr)
        if x == 0:
            answer += 1
            return
        if x > ln: return
        if x == ln:
            if '0' in arr:return
            else:
                answer += 1
                return
        answer += C[ln-1][x]
        answer %= mod
        #debug(ans, x)
        i = arr.find('1', arr.index('1')+1)
        if i < 0: 
            if x == 1: answer += 1
            return
        #debug("***")
        x -= 1
        arr = arr[i:]
        #cal2(x-1, arr[i:])

def cal(x):
    nonlocal answer
    answer = 0
    cal2(x, n)
    debug(answer)
    return answer % mod

def solve():
    if k == 0:return 1
    if len(a) == 0:return 0
    tmp = map(cal,a)
    debug(list(tmp))
    ans = reduce(lambda x,y:(x+y)%mod, map(cal, a))
    return ans if k != 1 else ans-1

try:
    print(solve())
except Exception as e:
    print(k, n[-30:])

#print(solve())


#l=[None,0,1,2,1,2,2,3,1,2,2,3,2,3,3,2,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,3,3,3,4,3,4,4,2,3]
ll=[[1],[2,4,8,16,32,64,128,256,512],[3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,65,66,68,71,72,75,77,78,80,83,85,86,89,90,92,96,99,101,102,105,106,108,113,114,116,120,129,130,132,135,136,139,141,142,144,147,149,150,153,154,156,160,163,165,166,169,170,172,177,178,180,184,192,195,197,198,201,202,204,209,210,212,216,225,226,228,232,240,255,257,258,260,263,264,267,269,270,272,275,277,278,281,282,284,288,291,293,294,297,298,300,305,306,308,312,320,323,325,326,329,330,332,337,338,340,344,353,354,356,360,368,383,384,387,389,390,393,394,396,401,402,404,408,417,418,420,424,432,447,449,450,452,456,464,479,480,495,503,507,509,510,513,514,516,519,520,523,525,526,528,531,533,534,537,538,540,544,547,549,550,553,554,556,561,562,564,568,576,579,581,582,585,586,588,593,594,596,600,609,610,612,616,624,639,640,643,645,646,649,650,652,657,658,660,664,673,674,676,680,688,703,705,706,708,712,720,735,736,751,759,763,765,766,768,771,773,774,777,778,780,785,786,788,792,801,802,804,808,816,831,833,834,836,840,848,863,864,879,887,891,893,894,897,898,900,904,912,927,928,943,951,955,957,958,960,975,983,987,989,990,999],[7,11,13,14,19,21,22,25,26,28,31,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,63,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,95,97,98,100,103,104,107,109,110,111,112,115,117,118,119,121,122,123,124,125,126,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,159,161,162,164,167,168,171,173,174,175,176,179,181,182,183,185,186,187,188,189,190,193,194,196,199,200,203,205,206,207,208,211,213,214,215,217,218,219,220,221,222,224,227,229,230,231,233,234,235,236,237,238,241,242,243,244,245,246,248,249,250,252,259,261,262,265,266,268,271,273,274,276,279,280,283,285,286,287,289,290,292,295,296,299,301,302,303,304,307,309,310,311,313,314,315,316,317,318,321,322,324,327,328,331,333,334,335,336,339,341,342,343,345,346,347,348,349,350,352,355,357,358,359,361,362,363,364,365,366,369,370,371,372,373,374,376,377,378,380,385,386,388,391,392,395,397,398,399,400,403,405,406,407,409,410,411,412,413,414,416,419,421,422,423,425,426,427,428,429,430,433,434,435,436,437,438,440,441,442,444,448,451,453,454,455,457,458,459,460,461,462,465,466,467,468,469,470,472,473,474,476,481,482,483,484,485,486,488,489,490,492,496,497,498,500,504,511,515,517,518,521,522,524,527,529,530,532,535,536,539,541,542,543,545,546,548,551,552,555,557,558,559,560,563,565,566,567,569,570,571,572,573,574,577,578,580,583,584,587,589,590,591,592,595,597,598,599,601,602,603,604,605,606,608,611,613,614,615,617,618,619,620,621,622,625,626,627,628,629,630,632,633,634,636,641,642,644,647,648,651,653,654,655,656,659,661,662,663,665,666,667,668,669,670,672,675,677,678,679,681,682,683,684,685,686,689,690,691,692,693,694,696,697,698,700,704,707,709,710,711,713,714,715,716,717,718,721,722,723,724,725,726,728,729,730,732,737,738,739,740,741,742,744,745,746,748,752,753,754,756,760,767,769,770,772,775,776,779,781,782,783,784,787,789,790,791,793,794,795,796,797,798,800,803,805,806,807,809,810,811,812,813,814,817,818,819,820,821,822,824,825,826,828,832,835,837,838,839,841,842,843,844,845,846,849,850,851,852,853,854,856,857,858,860,865,866,867,868,869,870,872,873,874,876,880,881,882,884,888,895,896,899,901,902,903,905,906,907,908,909,910,913,914,915,916,917,918,920,921,922,924,929,930,931,932,933,934,936,937,938,940,944,945,946,948,952,959,961,962,963,964,965,966,968,969,970,972,976,977,978,980,984,991,992,993,994,996,1000],[127,191,223,239,247,251,253,254,319,351,367,375,379,381,382,415,431,439,443,445,446,463,471,475,477,478,487,491,493,494,499,501,502,505,506,508,575,607,623,631,635,637,638,671,687,695,699,701,702,719,727,731,733,734,743,747,749,750,755,757,758,761,762,764,799,815,823,827,829,830,847,855,859,861,862,871,875,877,878,883,885,886,889,890,892,911,919,923,925,926,935,939,941,942,947,949,950,953,954,956,967,971,973,974,979,981,982,985,986,988,995,997,998]]
facts=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,227020758,178290591,674358851,789741546,425606191,660911389,557316307,146326063,72847302,602640637,860734560,657629300,440732388,459042011,394134213,35757887,36978716,109361473,390205642,486580460,57155068,943272305,14530444,523095984,354551275,472948359,444985875,799434881,776829897,626855450,954784168,10503098,472639410,741412713,846397273,627068824,726372166,318608048,249010336,948537388,272481214,713985458,269199917,75195247,286129051,595484846,133605669,16340084,996745124,798197261,286427093,331333826,536698543,422103593,280940535,103956247,172980994,108669496,715534167,518459667,847555432,719101534,932614679,878715114,661063309,562937745,472081547,766523501,88403147,249058005,671814275,432398708,753889928,834533360,604401816,187359437,674989781,749079870,166267694,296627743,586379910,119711155,372559648,765725963,275417893,990953332,104379182,437918130,229730822,432543683,551999041,407899865,829485531,925465677,24826746,681288554,260451868,649705284,117286020,136034149,371858732,391895154,67942395,881317771,114178486,473061257,294289191,314702675,79023409,640855835,825267159,333127002,640874963,750244778,281086141,979025803,294327705,262601384,400781066,903100348,112345444,54289391,329067736,753211788,190014235,221964248,853030262,424235847,817254014,50069176,159892119,24464975,547421354,923517131,757017312,38561392,745647373,847105173,912880234,757794602,942573301,156287339,224537377,27830567,369398991,365040172,41386942,621910678,127618458,674190056,892978365,448450838,994387759,68366839,417262036,100021558,903643190,619341229,907349424,64099836,89271551,533249769,318708924,92770232,420330952,818908938,584698880,245797665,489377057,66623751,192146349,354927971,661674180,71396619,351167662,19519994,689278845,962979640,929109959,389110882,98399701,89541861,460662776,289903466,110982403,974515647,928612402,722479105,218299090,96415872,572421883,774063320,682979494,693774784,611379287,166890807,880178425,837467962,705738750,616613957,338771924,497191232,896114138,560652457,661582322,224945188,262995829,859081981,857116478,279856786,408062844,406076419,367193638,985761614,767884817,77737051,801784560,410447512,813374614,702909132,777826615,11426636,685259446,721228129,931065383,593559607,860745086,578819198,495425745,893029457,6156532,502193801,37480384,220174401,383076669,3013247,750298503,574624441,230733683,144887710,656590378,773954850,358485371,772254339,469363737,95843299,823414273,87709482,892174648,749756145,185864756,68295241,98238739,131504392,111672419,928208089,687974198,753032165,71715287,506557931,290314197,546089425,174590825,187067364,817659471,309331349,303445769,964814732,112937795,848457973,113604679,263728612,162653895,519013648,956915940,591788795,26960558,818561771,201473695,830318534,283328761,298655153,103269519,567777414,629890782,707451727,528064896,419467694,259775012,452053078,972081682,512829263,412924123,354780756,917691336,648929514,519218426,957710940,848100261,607279584,78508462,651656900,271922065,927371945,976904514,655633282,147015495,44958071,431540693,956102180,821001984,4640954,508310043,709072863,866824584,318461564,773853828,371761455,53040744,609526889,972452623,799173814,723225821,3874155,305590228,289496343,139259591,348260611,756867525,848691744,101266155,835557082,267191274,448180160,518514435,443022120,614718802,151579195,204297074,912569551,137049249,515433810,979001276,524451820,229298431,88837724,892742699,387369393,840349900,206661672,18186411,619853562,246548548,236767938,893832644,930410696,321544423,971435684,402636244,780681725,194281388,661238608,964476271,643075362,439409780,96895678,723461710,915447882,785640606,114709392,933696835,539582134,739120141,300372431,244129985,722433522,26638091,388855420,42468156,647517040,474194942,832805846,958306874,489519451,339220689,9833277,923477502,390998217,790283925,694135631,736657340,609563281,873127083,489593220,264439147,891171227,489029295,502009550,325923608,280525558,857054649,820622208,558213940,216997416,487921842,951328535,606653379,794417402,449723904,783486165,414645478,809681447,114612567,824953206,255016498,147060381,88903008,228293174,394357308,362355866,900088886,638573794,779598451,904922263,451026166,549459329,212643744,563246709,391796933,174243175,189725986,238337196,60051478,782959006,982673239,237607992,685987666,694447544,195840153,519748540,446086975,523485236,185780714,716004996,214280883,140643728,555470704,516522055,116665689,899547947,490696549,683197147,686671136,988747143,744912554,619072836,345158054,224284246,637879131,78947725,342273666,237716550,915360466,711578771,423071394,228124918,271834959,480779410,254894593,859192972,990202578,258044399,151532640,644862529,48049425,448119239,130306338,850105179,401639970,606863861,183881380,837401090,513536652,714177614,946271680,243293343,403377310,688653593,15447678,754734307,631353768,202296846,159906516,912696536,737140518,467380526,896686075,309895051,356369955,461415686,706245266,10064183,183054210,455971702,737368289,956771035,564163693,365118309,226637659,304857172,440299843,717116122,485961418,615704083,476049473,354119987,329471814,620060202,251964959,45357250,175414082,671119137,48735782,122378970,717506435,18459328,949577729,771970076,635808197,608040366,165916428,258536202,902229110,617090616,548564593,613394864,753777984,577888302,416452176,881599549,524547188,599140122,522765386,657552586,256787840,287613719,776067801,597965522,458655497,764387515,350167935,494713961,513386012,576480762,864589772,86987059,495636228,512647986,721997962,982831380,162376799,204281975,462134806,189646394,425968575,209834628,494248765,664281698,947663843,540352769,25662122,986679150,207298711,477043799,24708053,528335066,189351697,717500453,42764755,316734785,823726196,293357001,547414377,258966410,602945692,561521296,351253952,752369730,174204566,871148004,302242737,554611874,540181425,349941261,414343943,921115587,959388563,227019335,708812719,793380997,342547759,324322556,458370547,356254978,809319893,159690374,848340820,971304725,180230004,103061704,207441144,443272953,45593686,541647240,612817107,849140508,109375794,906749744,159084460,541378020,692284266,908221578,720697998,363923522,819281897,701846632,479994712,196613531,29272489,792937812,859009553,202148261,385627435,115321267,612859231,132778909,173511339,782369566,322583903,324703286,31244274,433755056,109559692,871157455,350443931,592104988,197184362,141678010,649163959,746537855,954594407,850681817,703404350,467293824,684978431,565588709,378843675,825260479,749777538,850502015,387852091,412307507,307565279,914127155,864079609,845970807,414173935,638273833,664477235,173471099,480759791,839694748,190898355,956270620,957911348,43002811,628936576,966234409,667971950,236586166,954211897,223051884,21058295,656573222,631532535,809706350,984734695,314281677,311454037,640732448,434907794,175084834,434807109,973816812,488481268,844735329,917344075,314288693,459259162,992521062,667512257,603748166,679935673,833938466,933875943,522922384,981191471,457854178,112860028,484939649,611363777,627371454,844300972,962501388,738504183,631041465,29224765,334078303,211237785,626057542,900175080,728504100,450509755,575177363,905713570,416609984,874776027,334255451,683287462,999293262,474888472,317020697,180417613,591538360,879151833,605566485,569294094,970567518,896200922,943088633,145735679,884701203,949403596,749113557,78958680,850679027,665376978,686499745,426302291,842343474,708066168,962548572,349652428,833757979,492365420,136639914,76093131,591710464,208764552,166233017,498121245,545840935,26721664,736011124,880639351,137410283,42609708,235572009,981737748,718913567,909319027,906112184,298059463,274736280,217450848,351267027,149682364,249066734,11785215,333890217,774940233,302540697,519852435,802535369,620684620,306323295,752310997,848793393,883503040,569433124,254795373,855478464,660158704,87911700,944741410,351053939,2634663,134077016,736459220,4882454,969435081,120150411,922584286,828772112,106810765,371205161,17024731,960279329,389323593,23991206,744762405,684217429,479374977,963728237,3246420,688035746,381629444,752436308,274567573,440219140,702541058,919238277,563955926,467150839,5249506,399086000,833151662,847391187,655983283,337920422,866913758,675206635,549602585,963783662,324756002,393087771,731515248,787956453,550936813,398161393,631665856,442637251,454846959,348994181,88011024,513458067,60476466,9760396,403700900,990173371,519613195,945797344,114696834,327457551,905694736,143025346,289024806,451579463,325709522,18701196,326143996,49850509,619195074,414881030,850660769,880149960,651809429,592293509,810577782,929598726,835669318,731671946,529667681,285562083,293565850,686472980,274474950,282703792,889076915,56602629,546147347,255724802,873696194,831784350,110556728,279941051,667003092,302778600,803516696,772054724,165410893,531446229,958833885,703493734,68812272,481542542,722167619,172528691,173636402,356397518,390931659,311533827,53449710,959934024,259493848,215350798,907381983,791418522,896453666,530274270,443147787,468552325,410897594,491169384,314015783,406644587,772818684,721371094,596483817,922913559,78344520,173781169,485391881,326797438,209197264,227032260,183290649,293208856,909531571,778733890,346053132,674154326,75833611,738595509,449942130,545136258,334305223,589959631,51605154,128106265,85269691,347284647,656835568,934798619,602272125,976691718,647351010,456965253,143605060,148066754,588283108,104912143,240217288,49898584,251930392,868617755,690598708,880742077,200550782,935358746,104053488,348096605,394187502,726999264,278275958,153885020,653433530,364854920,922674021,65882280,762280792,84294078,29666249,250921311,659332228,420236707,614100318,959310571,676769211,355052615,567244231,840761673,557858783,627343983,461946676,22779421,756641425,641419708]
facts_inv=[1,1,500000004,166666668,41666667,808333339,301388891,900198419,487524805,831947206,283194722,571199524,380933296,490841026,320774361,821384963,738836565,514049213,639669405,402087866,120104394,862862120,130130097,179570875,799148792,791965957,761229465,917082579,282752951,699405279,123313510,649139150,957785605,604781386,958964165,170256120,671396008,261389083,243720767,211377457,230284438,469031331,654024560,317535457,393580354,297635121,202122504,366002609,861791727,854322286,57086446,138374245,98814890,662241795,956708188,762849245,960050886,16842998,379600744,752196628,279203279,250478744,971781922,888440989,92006891,262953954,367620517,856233148,659650492,328400734,261834298,102279357,626420551,159266036,785936033,757145819,470488764,58058296,590487931,361904913,517023815,623666965,775898383,33444559,512302915,711909451,833859418,262458156,412073391,746203077,108291146,902288920,444590100,843490222,455781814,720587182,986672790,267903845,992529638,545379091,875453797,751242122,732855320,463425783,917917562,427789694,494601793,929856098,360461633,462022587,631472937,708391653,979539218,150261410,966230370,704054182,781931507,664802838,73430533,244314544,735369293,204424541,157413317,90710678,403957347,35231659,341549460,435760235,26841877,287029784,832977158,494908226,18900820,428713543,234542640,890626248,477136961,324650637,415396022,556945299,311121040,775256183,97008847,909769299,860484515,247313688,97584341,197942752,622959077,816261476,218775078,61051491,388559552,270513463,930328016,535034378,939327150,802161325,87355452,76021104,300475134,921120970,141488402,117432445,836081911,411127772,279585109,331015482,251970332,113916985,971258342,929656488,889125916,178549862,909072132,142337556,23536009,73579300,595918989,327351505,474040845,682177026,267484491,181789534,164031466,579265039,169780996,589143218,907389066,354007352,970284256,753771127,915384231,880390598,520002017,689846169,600458403,815230759,706137534,732191651,538660962,47456025,599244836,111326330,657408467,412962971,375791085,784424117,527809735,930755077,237765502,688330647,526831752,551769167,745569020,26723577,264012611,623336468,599189621,669402697,589406380,862395510,571452236,262652254,206529699,414251246,621302001,764851556,933179180,287917815,979512693,56188367,340759435,756827299,7507809,544712803,794680992,674239165,82664871,130052992,267208556,113141945,12864223,559723725,842457890,921805957,885861006,35975146,40467642,554379392,778217523,182383338,405485651,139942632,890314741,678001239,811242198,707436745,425222626,905116696,126558142,441097927,852828624,326436613,232297110,604650182,671446058,10005416,522425397,518670730,38958040,830402065,800847072,376559882,110863358,113130413,279395402,246496014,986498194,953356631,314119133,22470175,961072596,215410152,155688065,70721713,297450078,812883107,541016959,1872031,644834046,476442732,755056316,91314186,326841207,285853701,396235995,476081606,270053967,311939982,581039804,985319076,135712978,964144274,904487323,678375373,515288812,705261532,807484621,122354320,419749533,972410777,211450036,949557355,18947635,222282375,48171780,378700860,623832397,478444619,510870143,876980910,810176965,748638324,113421724,440348993,863313960,855851119,438584915,828080811,720691159,71663720,48408626,843989221,837856261,23396586,696498209,699396142,558282241,447074582,748373754,670816350,949329879,230172975,253576086,513778485,518825953,716192587,608379868,932975307,856951364,238908695,952383270,413462845,749755550,255633116,371504590,575270325,736243777,7621849,202798951,842667039,502327813,12403107,546737375,494648599,151624724,395508517,384226928,242233679,35789821,275029085,239986639,890723831,812542048,364833448,745651158,442296160,329212426,335960985,66673582,971303612,458040065,136966163,279002518,756568843,351700958,866541869,396563255,517728958,965430081,680218496,838469951,144627151,576509210,798927877,640906388,538138307,199844570,847618664,622119051,373122494,767097325,617288087,395092300,433074305,67569149,815890839,568176207,776450314,850674275,408395804,136913583,801784300,794207214,262154718,34284026,400561835,433972639,573828101,184699592,812790266,404769648,582517190,392883298,497395023,656097176,460552924,608552698,486267026,331363414,476406879,202491684,432338321,344314146,993894982,649068571,532377735,925873015,756095388,83536581,782502356,467833719,201958994,113067476,982276563,417000623,683259514,595275137,339855849,540755239,602085936,629650637,694546695,783468170,990732904,300418276,153830238,781995268,886235290,762796169,704474617,834858176,120593647,291208178,185572492,867351020,704212748,633983365,436319797,679651749,574691409,884692149,583265738,954817023,25168036,437027667,13494817,926806481,260807531,473460019,215121540,398786562,665421923,247242609,357210812,375220601,951489166,260146496,562904189,803189606,115688778,402674167,664102792,62073083,931438538,989781133,54305395,845490579,408508000,817016,770460718,252530800,193344993,18240764,451521272,550299453,675641621,648967803,128976362,498292114,586102337,268722858,813389329,711699206,345071263,549118359,498160774,12544712,899831499,7499676,159323417,860458480,925163407,526574743,431479193,124394448,736478932,827152428,468482333,191449968,570982019,630772527,6811956,460686917,587776989,189529436,618602480,213045731,31935150,166725807,46518902,361709447,728106284,141044314,106680816,648547039,81624401,345039463,428679492,444415784,871949944,552304261,263204892,812749473,93356306,615275825,658196191,99745872,808765204,980015659,506203240,798053748,875307384,490913669,395559142,537801345,254916759,26857248,323421544,786532324,111710215,362083412,98363148,686582519,232498406,816375871,302974657,320593384,541140925,837139904,84057040,831759554,589762885,489023570,342716282,966455154,672855976,456926629,511811424,370359005,435482844,480465346,749545478,742002607,688642026,635383632,287496457,895129599,639223927,732732045,883082755,597812434,281256739,243843142,932634458,133552203,978803223,605228299,76527469,923076281,353392926,363322540,770576388,900277818,11219964,45472760,708339507,491437446,743928014,675393437,584018351,629556304,639854830,305512590,408488823,110876181,497784495,617034693,851537422,102938949,385266150,668331122,814641919,630622468,978945869,28268783,357972167,146329111,973624935,149958790,433931296,25598024,447940280,354732829,764891064,685394573,585294277,465409408,469130064,920721745,182673921,284022508,597678446,416816025,588422624,98457962,240636924,36839874,300511140,182273503,581213731,455560749,864940520,856724314,261438685,740632796,674273817,942626165,174802133,374887767,194299387,742848665,907493095,441999251,492506669,611675310,290416066,970929824,883609623,223358251,807963821,422005815,659475855,461490465,664907290,263359925,173600234,665950005,716496304,824226812,899890349,390028746,771125588,145203352,452007490,325362082,146808268,736600017,245688986,146065271,957412368,898799739,278661168,704941285,610928999,81601883,483849511,959722958,846205539,512459448,477514011,94771790,785546670,950680044,61469483,942823288,676349828,399270685,202224300,83614201,27855221,178708942,736070142,898806733,147446631,252269212,554679879,911476215,87670064,942585856,185967971,834953514,366759830,422843000,170643325,93981853,572719111,985870900,598086433,218375794,859943833,859649526,91331965,695015236,607644320,732718027,917982226,747216559,979635810,561306185,34036360,223449518,94586255,423202372,442944642,611697021,200279654,277309078,618283679,820550379,353246455,521460957,68835467,668938271,630939793,166620027,751195077,59571869,663276431,490471791,292464946,386389206,728831039,100424847,231097324,77617394,253639149,723976405,560621283,219949516,322944880,693507607,78791198,119998459,265121019,385833490,175839688,127126701,357575575,462477947,523972795,85257542,474256318,882209397,465260644,945308123,444097002,744917420,375150087,199218939,962795536,153320195,574288074,366385933,970641480,460261345,165378268,54660122,796112070,75056929,684432874,318576890,508386937,736496795,933419021,301388996,795962538,981413164,518902828,825023058,764707707,274652931,632168477,715573025,516018880,296024238,427201967,100757491,425935778,453525227,714143838,325377579,154052075,164453301,661274799,281891479,854578132,707463702,54478503,560779145,542878457,842687510,21165703,595996646,257510057,793448599,603061927,924060221,392136705,100461338,471328395,891398279,205030949,652464912,835850842,87425060,823905986,380913646,278673941,927068232,520240501,876473603,136589194,511732167,687296805,683241687,350269024,968145478,892943787,218267753,631708693,575265725,844874308,490669196,539989340,283721451,422216333,634877244,154305891,30857166,70409600,192823595,593649861,218997343,408157062,510618691,46798894,349151803,787794327,112121118,212247051,734542883,558493333,135971470,553224553,555304942,877988083,353984399,287379295,128097089,213238733,686489183,584370424,478522537,386164116,728903056,854166382,496535429,200766267,471649197,622910706,125683017,956326056,20739963,301662013,197927580,561829805,470110929,409651919,25445274,530972257,693634465,812235796,433779479,246955439,273484835,533196859,434841810,150091327,794785050,966482053,130865325,820075960,424860898,894572050,601383094,45465724,85336318,672082365,48587322,356055887,859189025,162098823,439790362,893587086,428005909,694221764,21829348,71677376,928496509,456286540,290395261,680262749,924193154,292067220,171853628,296940288,150623112,455840069,180683168,811842548,508120422,642272196,544234726,650304911,229451663,921643700,798472778,749018037,226545381,765423842,718894474,717080061,749196186,489999179,806854513,378512648,701818525,88561613,592947516,719258871,280773178,426531817,513644853,265496088,511425456,854621511,704306302,284837521,431600849,280960245,932742910,291976581,677356118,77062670,110519140,832608350,207247104,180387636,52180388]

import sys
sys.setrecursionlimit(10000)
mod=1000000007

def combi(n,r):
    if r==0 or r==n:
        return 1
    if r<0 or n<r:
        return 0
    return (((facts[n]*facts_inv[r])%mod)*facts_inv[n-r])%mod

def solve(n,m,first_time=True):
    if n=="1":
        return 1 if (m==0 or m==1) else 0
    if m<0 or len(n)<m:
        return 0
    if m==0:
        return 1
    ind=n.find("1",1)
    if ind==-1:
        if first_time:
            return combi(len(n)-1,m)%mod
        else:
            return len(n) if m==1 else combi(len(n)-1,m)%mod
    else:
        if first_time and m==1:
            return (solve(n[ind:],m-1,False)+combi(len(n)-1,m)-1)%mod
        return (solve(n[ind:],m-1,False)+combi(len(n)-1,m))%mod

n=input()
k=int(input())
if k>5:
    print(0)
elif k==0:
    print(1)
elif k==1 and n=="1":
    print(0)
else:
    res=0
    for m in ll[k-1]:
        res+=solve(n,m)
        res%=mod
    print(res)


dpc=[1]
dpci=[]
for i in range(1,2000):
    dpc.append((dpc[i-1]*i)%1000000007)
def modInverse(a, m) :
    m0 = m
    y = 0
    x = 1
    if (m == 1) :
        return 0
    while (a > 1) :
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if (x < 0) :
        x = x + m0
    return x
for i in dpc:
    dpci.append(modInverse(i,1000000007))
def c(n,r):
    if(r<0):
        return 0
    if(n<r):
        return 0
    if(n<0):
        return 0
    return dpc[n]*dpci[r]*dpci[n-r]

dp={1:0}
def f(n):
    x=n
    b=0
    while x!=0:
        x=x&(x-1)
        b+=1
    dp[n]=dp[b]+1
for i in range(2,1001):
    f(i)
a=[[],[],[],[],[]]
for i in dp:
    a[dp[i]].append(i)
n=input()
l=len(n)
x=[]
for i in range(l):
    if n[i]=='1':
        x.append(i)
#print(l)
k=int(input())
if k>5:
    print(0)
elif k==0:
    print(1)
else:
    ans=0
    for i in a[k-1]:
        r=0
        for j in x:
            if i-r<0:
                break
            xy=c(l-j-1,i-r)
            #print(l-j-1,i-r,xy)
            ans=(ans+xy)%1000000007
            r+=1
    if len(x) in a[k-1] and len(x)!=1:
        ans+=1
    if len(x)>1 and k==1:
        ans-=1
    print(ans)

R = lambda: map(int, input().split())
mod = 10 ** 9 + 7
maxn = 1001
c = [[0 for j in range(maxn)] for i in range(maxn)]
for i in range(maxn):
    c[i][0] = 1
for i in range(1, maxn):
    for j in range(i + 1):
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
arr = list(map(int, input()))
k = int(input())
if k == 0:
    print(1 if arr.count(1) else 0)
    return
ops = [0] * (maxn + 1)
ans = 0
for i in range(2, maxn):
    cnt = bin(i).count('1')
    ops[i] = ops[cnt] + 1
for i in range(1, maxn):
    if ops[i] == k - 1:
        oc = i
        for j, x in enumerate(arr):
            if x and oc >= 0:
                ans = (ans + c[len(arr) - j - 1][oc]) % mod
                oc -= 1
        ans = (ans + 1) % mod if arr.count(1) == i else ans
if k == 1:
    ans = (ans + mod - 1) % mod
print(ans)

import sys
import math
from collections import defaultdict,deque
import heapq
fact=[1]
mod=10**9+7
for i in range(1,1005):
    fact.append((i*fact[-1])%mod)
#print(fact,'fact')
def comb(n,k,fact):
    #print(n,'n',k,'k')
    x=fact[n]
    y=pow(fact[k],mod-2,mod)
    z=pow(fact[n-k],mod-2,mod)
    #print(x,'x',y,'y',z,'z')
    
    return (x*(y*z))%mod
def getset(num):
    cnt=0
    while num>0:
        cnt+=num%2
        num=num>>1
    return cnt
def get(s,bits):
    #print(s,'s',bits,'bits')
    n=len(s)
    #print(n,'n')
    if n!=0 and bits==0:
        return 1
    if n==0 and bits==0:
        return 1
    if n==0:
        return 0
    if s[0]=='1':
        ans=0
        if n-1>=bits:
            ans+=comb(n-1,bits,fact)
            #print(comb(n-1,bits,fact),'comb')
        x=get(s[1:],bits-1)
        #print(x,'x',s,'s',bits-1,'bitts')
        ans+=x
        ans%=mod
        #print(s,'s',ans,bits)
        return ans
    x=get(s[1:],bits)
    x%=mod
    #print(s,'s',x,bits)
    return x
#t=int(sys.stdin.readline())
num=sys.stdin.readline()[:-1]
m=len(num)
n=0
#print(m,'m')
for i in range(m):
    if num[i]=='1':
        n=(n<<1)+1
    else:
        n=n<<1
#print(n,'nnnn')
k=int(sys.stdin.readline()[:-1])
if k==0:
    print(1)
    return
dic=defaultdict(list)
for i in range(2,1001):
    x=getset(i)
    cnt=0
    while x!=1:
        y=getset(x)
        cnt+=1
        x=y
    dic[cnt+1].append(i)
#print(dic,'dic')
ans=0
'''for i in dic[k]:
    if i<=n:
        ans+=1'''
#ans+=len(dic[k])
#print(n,'n')
#print(num,'num')
s=num
#print(s,'s')
#print(len(s))
dic[0]=[1]
#print(dic[k-1])
for j in dic[k-1]:
    if j<=n:
        #print(s,'s')
        x=get(s,j)
        #print(x,'xxxxxxxx')
        #print(j,'j')
        #print(x,'x',j,'j',k-1,'k-1')
        ans+=x
        #print(x,'x',k-1,'j',j,'j')
        ans%=mod
#ans=get(s,k-1)
if s=='1' and k==1:
    print(0)
    return
if k==1:
    ans-=1
print(ans)


MOD = 1000000007
OBRAT = [-1] * 2000
CC = {}
FACT = [-1] * 2000
OBRAT_FACT = [-1] * 2000


def obrat(k):
    if OBRAT[k] == -1:
        OBRAT[k] = fast_pow(k, MOD - 2)
    return OBRAT[k]


def c(n, k):
    if (n, k) in CC:
        return CC[(n, k)]
    res = fact(n)
    res = (res * obrat_fact(k)) % MOD
    res = (res * obrat_fact(n - k)) % MOD
    CC[(n, k)] = res
    return res


def obrat_fact(k):
    if OBRAT_FACT[k] != -1:
        return OBRAT_FACT[k]
    res = 1
    for i in range(2, k + 1):
        res = (res * obrat(i)) % MOD
    OBRAT_FACT[k] = res
    return res


def fact(n):
    if FACT[n] != -1:
        return FACT[n]
    res = 1
    for i in range(2, n + 1):
        res = (res * i) % MOD
    FACT[n] = res
    return res


def fast_pow(x, y):
    if y == 0:
        return 1
    p = fast_pow(x, y // 2) % MOD
    p = p * p % MOD
    if y % 2:
        p = p * x % MOD
    return p


s = input()
k = int(input())
n = len(s)

if k == 1:
    print(n - 1)
    return
if k == 0:
    print(1)
    return

moves = [0] * 1025
moves[1] = 0
for i in range(2, 1024):
    ii = i
    ones = 0
    while ii > 0:
        if ii % 2 == 1:
            ones += 1
        ii //= 2
    moves[i] = moves[ones] + 1

if n < 10:
    d = 1
    a = 0
    for i in range(n - 1, -1, -1):
        a += d * int(s[i])
        d *= 2
    res = 0
    for i in range(2, a + 1):
        if moves[i] == k:
            res += 1
    print(res)
    return

res = 0
if moves[s.count('1')] == k - 1:
    res += 1
for i in range(1, 1024):
    ki = moves[i]
    if ki != k - 1:
        continue
    m = n - 1
    j = 0
    while m >= i and i >= 0 and m >= 0:
        res = (res + c(m, i)) % MOD
        i -= 1
        j += 1
        while j < n and s[j] != '1':
            j += 1
        m = n - 1 - j

print(res)