abc154e-test.py

def slow_solve(N, K):
    result = 0
    for i in range(1, int(N) + 1):
        s = str(i)
        if len(s) - s.count('0') == K:
            result += 1
    return result

def fast_solve(N, K):
    def f(N, K, f):
        t = [0] * (K + 2)
        if f:
            t[0] = 1
            t[1] = int(N[0])
        else:
            t[1] = 1
        for i in range(1, len(N)):
            j = int(N[i])
            for k in range(K, -1, -1):
                t[k + 1] += t[k] * j
        return t[K]

    if int(N[0]) == '1':
        return f(N, K, False) + f('9' * (len(N) - 1), K, True)
    else:
        return f(N, K, False) + f(str(int(N[0]) - 1) + '9' * (len(N) - 1), K, True)


N = input()
K = int(input())

for K in range(1, 4):
    for N in range(1, 100):
        a = slow_solve(str(N), K)
        b = fast_solve(str(N), K)
        if a != b:
            print('BUG: %d != %d from N, K = %d, %d' % (a, b, N, K))