Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())

# 桁数調べる
# tmp = N
# digit = 1
# while tmp >= 10:
#     tmp //= 10
#     digit += 1
# print(digit)

if K > len(str(N)):
    print(0)
    exit()

if K == 1:  # done
    N = str(N)
    ans = (len(N)-1) * 9
    ans += int(N[0])
    print(ans)

elif K == 2:
    N = str(N)
    # 最上位を避けた, (n-1)C2 * 9の二乗
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位の桁2つのみ, 最上位がN[0]のパターン, N[0]の1通りと, N[1]通り
    ans += 1 * int(N[1])
    # 最上位の桁2つののみ, 最上位!=N[0]のパターン
    ans += (int(N[0])-1) * 9
    # 最上位とその他(二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * 9
    print(ans)
elif K == 3:
    print(AAA)
    N = str(N)
    # 最上位を避けた選び方, n-1C3 * 9の三乗
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他, 最上位がN[0]の場合
    ans += 1 * int(N[1]) * (len(N)-2) * 9
    # 上位二桁とその他, 最上位!=N[0]の場合, int(N[0])-1なのはN[0]のパターンを除くため
    ans += (int(N[0])-1) * 9 * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)


Fixed submission:
N = str(input())
K = int(input())
# dp[i][j][k] :=  i桁目まで決めたとき、非ゼロの個数がj個で、
# k->0: そこまでの桁はNと完全一致, k->1: そこまでの桁ですでにN未満であることが確定
# しているときのパターン数
# kは0or1の二通り, jは0~KのK+1通り, iは0~NのN+1通り
dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    x = int(N[i])  # Nは文字列であることに注意
    for j in range(K):
        dp[i+1][j+1][1] += dp[i][j][1]*9  # すでにN未満が確定している世界線で、jの数を増やすから9倍される
        dp[i+1][j][1] += dp[i][j][1]  # すでにN未満が確定している世界線で、jの数は変えない
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]  # 新しい桁に0を埋め込んで、N以下になる道を選んだ世界線
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)  # 新しい桁に1~(x-1)のx-1通りを埋め込んでN以下になる道を選んだ世界線
            dp[i+1][j+1][0] += dp[i][j][0]  # 新しい桁にxを埋め込んでNのままであり続ける世界線
        else:
            dp[i+1][j][0] += dp[i][j][0]  # xが0の時は、Nのままであり続ける世界線は0しか入れようがない
    dp[i+1][K][1] += dp[i][K][1]
    dp[i+1][K][x>0] += dp[i][K][0]
print(sum(dp[len(N)][K]))

Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())

if K == 1:
    N = str(N)
    ans = (len(N)-1) * (len(N)-2) * 9
    ans += int(N[0])
    print(ans)
    # N = str(N)
    # ans = 9*(len(N)-1)+int(N[0])
    # print(ans)
elif K == 2:
    N = str(N)
    # 最上位を避けた
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位ともう一つ
    ans += (int(N[0])-1) * (len(N)-1) * 9
    # 最上位の桁のみを選ぶ場合
    ans += 1 * int(N[1])
    # 最上位+何か
    ans += 1 * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他
    ans += int(N[0]) * int(N[1]) * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)


Fixed submission:
N = str(input())
K = int(input())
# dp[i][j][k] :=  i桁目まで決めたとき、非ゼロの個数がj個で、
# k->0: そこまでの桁はNと完全一致, k->1: そこまでの桁ですでにN未満であることが確定
# しているときのパターン数
# kは0or1の二通り, jは0~KのK+1通り, iは0~NのN+1通り
dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    x = int(N[i])  # Nは文字列であることに注意
    for j in range(K):
        dp[i+1][j+1][1] += dp[i][j][1]*9  # すでにN未満が確定している世界線で、jの数を増やすから9倍される
        dp[i+1][j][1] += dp[i][j][1]  # すでにN未満が確定している世界線で、jの数は変えない
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]  # 新しい桁に0を埋め込んで、N以下になる道を選んだ世界線
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)  # 新しい桁に1~(x-1)のx-1通りを埋め込んでN以下になる道を選んだ世界線
            dp[i+1][j+1][0] += dp[i][j][0]  # 新しい桁にxを埋め込んでNのままであり続ける世界線
        else:
            dp[i+1][j][0] += dp[i][j][0]  # xが0の時は、Nのままであり続ける世界線は0しか入れようがない
    dp[i+1][K][1] += dp[i][K][1]
    dp[i+1][K][x>0] += dp[i][K][0]
print(sum(dp[len(N)][K]))