#  https://[Log in to view URL]
from functools import cache
from math import comb

@cache
def T(n, k):
    if n < k or k < 0:
        return 0
    return 2**(n+1) - 1 if k == 0 else T(n - 1, k) + T(n - 1, k - 1) + comb(n, k) * 2**n
    
@cache
def f(a, k):
    if k <= 0:
        return 0
    m = 1
    while m < len(a):
        if a[m] == '1':
            break
        m += 1
    print("m :", m)
    if m < k - 1:
        return 0
    print("T :", T(len(a) - 2, k - 1))
    return comb(len(a) - 1, k) + f(a[m:], k - 1)

r = f("1011", 2)
print(r)