n = input()
k = int(input())
#nより小さいことが確定しているdp
#dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
dp_0 = [[0 for i in range(k+1)] for j in range(len(n))]
#nより小さいことが確定していないdp
#dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
dp_1 = [[0 for i in range(k+1)] for j in range(len(n))]
dp_0[0][0] = 1
dp_0[0][1] = int(n[0]) - 1
dp_1[0][1] = 1
for i in range(1,len(n)):
    dp_0[i][0] = 1
    for j in range(1,k+1):
    #今回の桁が0でないことを想定
        if n[i] != '0':
            #0を使う場合と使わない場合両方考える
            #まずは使わない場合
            dp_0[i][j] += dp_0[i-1][j-1] * 9 + dp_1[i-1][j-1] * (int(n[i]) - 1)
            dp_1[i][j] += dp_1[i-1][j-1]
            #0を使う場合。この時はjが変化しない。なぜなら0を使うか
            #dp_1の更新は無し。
            #なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
            dp_0[i][j] += dp_0[i-1][j] + dp_1[i-1][j]
        else:
            #今回の桁が0の場合 
            #dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
            #さっきの桁まででnより小さいことが確定しないものが
            #今回の桁の決め方で確定することはないから。
            dp_0[i][j] = dp_0[i-1][j-1] * 9 + dp_0[i-1][j]
            dp_1[i][j] = dp_1[i-1][j]
print(dp_0)
print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])


3c68c83cb075203be12252f6edba368c5cced140
<mask token>

<mask token>
for i in range(1, len(n)):
    dp_0[i][0] = 1
    for j in range(1, k + 1):
        if n[i] != '0':
            dp_0[i][j] += dp_0[i - 1][j - 1] * 9 + dp_1[i - 1][j - 1] * (int
                (n[i]) - 1)
            dp_1[i][j] += dp_1[i - 1][j - 1]
            dp_0[i][j] += dp_0[i - 1][j] + dp_1[i - 1][j]
        else:
            dp_0[i][j] = dp_0[i - 1][j - 1] * 9 + dp_0[i - 1][j]
            dp_1[i][j] = dp_1[i - 1][j]
print(dp_0)
print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])

n = input()
k = int(input())
dp_0 = [[(0) for i in range(k + 1)] for j in range(len(n))]
dp_1 = [[(0) for i in range(k + 1)] for j in range(len(n))]
dp_0[0][0] = 1
dp_0[0][1] = int(n[0]) - 1
dp_1[0][1] = 1
for i in range(1, len(n)):
    dp_0[i][0] = 1
    for j in range(1, k + 1):
        if n[i] != '0':
            dp_0[i][j] += dp_0[i - 1][j - 1] * 9 + dp_1[i - 1][j - 1] * (int
                (n[i]) - 1)
            dp_1[i][j] += dp_1[i - 1][j - 1]
            dp_0[i][j] += dp_0[i - 1][j] + dp_1[i - 1][j]
        else:
            dp_0[i][j] = dp_0[i - 1][j - 1] * 9 + dp_0[i - 1][j]
            dp_1[i][j] = dp_1[i - 1][j]
print(dp_0)
print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])

n = input()
k = int(input())
#nより小さいことが確定しているdp
#dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
dp_0 = [[0 for i in range(k+1)] for j in range(len(n))]
#nより小さいことが確定していないdp
#dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
dp_1 = [[0 for i in range(k+1)] for j in range(len(n))]
dp_0[0][0] = 1
dp_0[0][1] = int(n[0]) - 1
dp_1[0][1] = 1
for i in range(1,len(n)):
    dp_0[i][0] = 1
    for j in range(1,k+1):
    #今回の桁が0でないことを想定
        if n[i] != '0':
            #0を使う場合と使わない場合両方考える
            #まずは使わない場合
            dp_0[i][j] += dp_0[i-1][j-1] * 9 + dp_1[i-1][j-1] * (int(n[i]) - 1)
            dp_1[i][j] += dp_1[i-1][j-1]
            #0を使う場合。この時はjが変化しない。なぜなら0を使うか
            #dp_1の更新は無し。
            #なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
            dp_0[i][j] += dp_0[i-1][j] + dp_1[i-1][j]
        else:
            #今回の桁が0の場合 
            #dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
            #さっきの桁まででnより小さいことが確定しないものが
            #今回の桁の決め方で確定することはないから。
            dp_0[i][j] = dp_0[i-1][j-1] * 9 + dp_0[i-1][j]
            dp_1[i][j] = dp_1[i-1][j]
print(dp_0)
print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])

