Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

N, K = map(int,read().split())

def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

# F(100, 1), F(25, 2), F(314159, 2)

print(F(N, K))


Fixed submission:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        # 残りの桁でK個使える時
        if (lenN - i) >= k:
            return comb(lenN - i, k) * (9 ** k)
        # 無理なら 0
        else:
            return 0
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i+1, k-1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        return comb(lenN - i, k) * (9 ** k)
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i + 1, k - 1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)


Fixed submission:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        # 残りの桁でK個使える時
        if (lenN - i) >= k:
            return comb(lenN - i, k) * (9 ** k)
        # 無理なら 0
        else:
            return 0
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i+1, k-1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)