124 周赛

第三题

M=10**9+7
R=10**3
F=[1]*(R+1)
for i in range(2,R+1):
    F[i]=(F[i-1]*i)%M
Fhyp=[1]*(R+1)
Fhyp[R]=pow(F[R],M-2,M)
for i in range(R-1,-1,-1):
    Fhyp[i]=(Fhyp[i+1]*(i+1))%M
def C(n,k):
    if n<0 or k<0 or n<k:
        return 0
    return (F[n]*Fhyp[n-k]*Fhyp[k])%M


# 返回值 res，表示数字 x 经过 res 轮转换后，变为 1
def g(x):
    if x==1:
        return 0
    return 1+g(bin(x).count('1'))

# 二进制：从右到左计算
n=[int(e) for e in input()[::-1]]
k=int(input())

if k==0:
    print(1)
elif k == 1:
    print(len(n) - 1)
else:
    # 先计算 n 上哪些位是 1
    nSetIndex = [i for i in range(len(n)) if n[i] == 1]
    # n 身上 1 的数量
    nSetNum = len(nSetIndex)

    # 所以这里只判断 k-1，原因是，只要一个数字 n 的二进制上有 j 个 1，那么这个数字就是易变数。
    J=[j for j in range(1,1000) if g(j)==k-1]

    s = 1 if g(nSetNum) == k-1 else 0

    for i in range(nSetNum):
        bitsLen = nSetIndex[i]
        for j in J:
            # 求：从 bitsLen 位中，设置 j - (nSetNum - 1 - i) 位为 1 的可能的结果数量
            s += C(bitsLen, j - (nSetNum - 1 - i))

    print(s % M)