Problem:
 Score : 500 points    Problem Statement Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.      Constraints  1 \leq N < 10^{100}  1 \leq K \leq 3         Input Input is given from Standard Input in the following format:  N  K       Output Print the count.        Sample Input 1 100
1      Sample Output 1 19  The following 19 integers satisfy the condition:   1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100        Sample Input 2 25
2      Sample Output 2 14  The following 14 integers satisfy the condition:   11,12,13,14,15,16,17,18,19,21,22,23,24,25        Sample Input 3 314159
2      Sample Output 3 937       Sample Input 4 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3      Sample Output 4 117879300

Solution (Python):
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def calc(n, k):
    if n < 10**(k-1):
        ans = 0
    elif n == 0:
        ans=0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                
        
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        elif k==1:
            ans += 1
    
    return ans
    

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

tot = calc(N,K)

print(tot)

Solution (Python):
N = int(input())
K = int(input())
def nonzero1(N):
    m = len(str(N))
    a = int(str(N)[-m]) 
    return a + 9*(m-1)
def nonzero2(N):
    m = len(str(N))
    a = int(str(N)[-m])
    n = N - a * (10**(m-1))
    s = ((m-1)*(m-2)*9*9)//2 + (m-1)*(a-1)*9
    return s + nonzero1(n)
def nonzero3(N):
    m = len(str(N))
    a = int(str(N)[-m])
    n = N - a * (10**(m-1))
    s = ((m-1)*(m-2)*(m-3)*9*9*9)//6 +((m-1)*(m-2)*9*9*(a-1))//2
    return s + nonzero2(n)
if K == 1:
    print(nonzero1(N))
elif K == 2:
    print(nonzero2(N))
else:
    print(nonzero3(N))

Solution (Python):
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = input()
k = int(input())

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    cnt = 0
    for c in n:
        if c != "0":
            cnt += 1
    return cnt

ans = 0
if cnt(n) == k:
    ans += 1


for i in range(len(n)):
    if int(n[i]) == 0:
        continue
    if len(n)-i > k:
        ans += calc(i, k)
    k -= 1
    if k < 0:
        break
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)
print(ans)

Solution (Python):
import sys 
N = list(input())
K = int(input())

L = len(N)
if K>L:
    print(0)
    sys.exit()

def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        L2 -= 1
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(ans))

Solution (Python):
N_str=input()
K=int(input())


digit_N=len(N_str)




dp=[[[0]*(K+1) for _ in range(digit_N)] for _ in range(2)]
dp[0][0][0]=1
dp[0][0][1]=int(N_str[0])-1
dp[1][0][1]=1


for j in range(1,digit_N):
  digit=int(N_str[j])
  for k in range(K+1):
    if digit==0:
      if k==0:
        dp[0][j][0]=dp[0][j-1][0]
      else:
        dp[0][j][k]=dp[0][j-1][k]+9*dp[0][j-1][k-1]
        dp[1][j][k]=dp[1][j-1][k]
    else:
      if k==0:
        dp[0][j][0]=dp[0][j-1][0]
      else:
        dp[0][j][k]=dp[0][j-1][k]+9*dp[0][j-1][k-1]+dp[1][j-1][k]+(digit-1)*dp[1][j-1][k-1]
        dp[1][j][k]=dp[1][j-1][k-1]
    

print(dp[0][-1][K]+dp[1][-1][K])

Solution (Python):
s = input()
d = len(s)
n = int(s)
k = int(input())

top = int(s[0])



def k_2(s):
    d = len(s)
    top = int(s[0])
    first_non_zero = -1
    first_pos = -1
    for i in range(1, d):
        if s[i] != '0':
            first_non_zero = int(s[i])
            first_pos = d - i
            break
    x = ((d-2) * (d-1) // 2) * 81
    y =  (top-1) * 9 * (d-1)
    z = first_non_zero + (first_pos-1) * 9 if first_pos >= 0 else 0
    return (x+y+z)    


if k == 1:
    print((d-1) * 9 + top)

elif k == 2:
    print(k_2(s))

else:
    x = ((9 ** 3) * (((d-3)*(d-2)*(2*d-5) // 6) + ((d-3)*(d-2) // 2)) //2)
    y = (top-1) * 81 * ((d-1)*(d-2) // 2)
    
    first_non_zero = -1
    ind = -1
    for i in range(1, d):
        if s[i] != '0':
            ind = i
            break
    z = k_2(s[ind:])
    
    
    
    print(x + y + z)

Solution (Python):
def make_num(n, k):
    if k == 0 or len(n)<k:
        return 0
    else:
        if int(n[0]) == 0:
            return make_num(n[1:], k)
        else:
            ln = len(n)
            if k == 3:
                return (((ln-1)*(ln-2)*(ln-3))//6)*(9**3) + (int(n[0])-1)*81*(((ln-1)*(ln-2))//2) + make_num(n[1:], k-1)
            elif k == 2:
                return (((ln-1)*(ln-2))//2)*81 + (int(n[0])-1)*9*(ln-1)  + make_num(n[1:], k-1)
            elif k == 1:
                return 9 * (ln-1) + int(n[0])

n = list(input())
k = int(input())

print(make_num(n,k))

Solution (Python):
n = int(input())
k = int(input())
m = len(list(str(n)))
n0 = list(str(n))
for i in range(m):
    n0[i] = int(n0[i])
ans = 0
comb = 1
if k < m:
    for j in range(k):
        comb *= (m-1-j)
        comb //= (j+1)
    ans += comb*(9**k)

if k == 1:
    ans += n0[0]
elif k == 2:
    if m >= 2:
        ans += (n0[0]-1)*9*(m-1)
        c = 1
        while n0[c] == 0 and c < m-1:
            c += 1
        if n0[c] > 0:
            ans += n0[c]
            ans += 9*(m-c-1)
    else:
        ans = 0
else:
    if m >= 3:
        ans += (n0[0]-1)*9*9*(m-1)*(m-2)//2
        c = 1
        while n0[c] == 0 and c <= m-2:
            c += 1
        if c < m-1:
            ans += (n0[c]-1)*9*(m-c-1)
            ans += 9*9*(m-c-1)*(m-c-2)//2
            c1 = c+1
            while n0[c1] == 0 and c1 < m-1:
                c1 += 1
            if n0[c1] > 0:
                ans += n0[c1]
                ans += 9*(m-c1-1)
    else:
        ans = 0
print(ans)

Solution (Python):
import sys
n=list(input())
N=len(n)
k=int(input())
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

def s1(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s1(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=(N-1)*9
    ans+=x
    return ans

def s2(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s2(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2))*81//2
    ans+=((x-1)*(N-1))*9
    m2=m[1:N+1]
    ans+=s1(m2)
    return ans
  
def s3(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s3(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2)*(N-3)*729)//6
    ans+=((x-1)*(N-1)*(N-2)*81)//2
    m2=m[1:N+1]
    ans+=s2(m2)
    return ans

if k==1:
  print(s1(n))
  sys.exit()

if k==2:
  print(s2(n))
  sys.exit()

if k==3:
  print(s3(n))
  sys.exit()

Solution (Python):
import itertools
import math

def solve():
  N = int(input())
  K = int(input())
  log_N = math.ceil(math.log10(N+1))
  digit_table = range(0,log_N)
  ret = 0
  for comb in itertools.combinations(digit_table, K):
    num = 0
    stack = [0]
    next_stack = []
    log_N
    if sum(9*(10**c) for c in comb) <= N: 
      ret += 9**K
      continue
    for c in comb:
      while stack:
        num_base = stack.pop()
        for d in range(1,10):
          num = num_base+d*10**c

          
          if c == comb[-1]:
            if num <= N: 
              
              ret += 1
          else:
            next_stack.append(num)

      stack = next_stack
      next_stack = []

  print(ret)
  
solve()

Solution (Python):
N=int(input())
K = int(input())
def one(N):
    n = list(str(N))
    A = (len(n)-1)*9
    A += int(n[0])
    return A

def two(N):
    n = list(str(N))
    r = len(n)
    A = (int(n[0])-1)*(r-1)*9 
    A = A + (r-2)*(r-1)*81/2  
    A = A + one(N%(10**(r-1)))
    return(A)

if K==1:
    print(int(one(N)))

elif K==2:
    print(int(two(N)))

elif K==3:
    n = list(str(N))
    r = len(n)
    A = two(10**(r-1)-1)*(int(n[0])-1)
    A = A + two(N%(10**(r-1)))
    A = A + (r-2)*(r-1)*(r-3)*81*9/6
    print(int(A))

Solution (Python):

def solve(n,k):
    for i in range(len(n)):
        if n[i] != 0:
            break
    n = n[i:]
    if n == []:
        return 0
    l = len(n)
    ans = 0
    
    tmp = 1
    for i in range(1, k+1):
        tmp = tmp*9*(l-i)
    for i in range(1, k+1):
        tmp = tmp // i
    ans += tmp

    
    tmp = n[0]-1
    for i in range(1, k):
        tmp = tmp*9*(l-i)
    for i in range(1, k):
        tmp = tmp // i
    ans += tmp

    
    tmp = 0
    if k == 3:
        tmp += solve(n[1:],k-1)

    elif k == 2:
        for i in range(1, l):
            if n[i] != 0:
                tmp += n[i] + 9*(l-i-1)
                break
    else:
        tmp += 1
    ans += tmp
    return ans

n = list(map(int, input()))
k = int(input())

print(solve(n,k))

Solution (Python):
n=int(input())
k=int(input())
d=len(str(n))
from math import factorial as f
def c(n):
  if n<2:
    return 0
  else:
    return f(n)//(f(n-2)*f(2))
def kk(n):
  dd=len(str(n))
  s=9*(dd-1)
  s+=int(str(n)[0])
  return s
def kkk(n):
  d=len(str(n))
  s=81*(d-1)*(d-2)//2
  s+=9*(d-1)*(int(str(n)[0])-1)
  s+=kk(int(str(n)[1:]))
  return s

if d==1 and k!=1:
  print(0)
else:
  if k==1:
    ans=kk(n)
  elif k==2:
    ans=kkk(n)
  else:
    t=0
    for i in range(2,d-1):
      t+=c(i)
    ans=729*t
    ans+=81*c(d-1)*(int(str(n)[0])-1)
    ans+=kkk(int(str(n)[1:]))
  print(ans)

Solution (Python):
def count(keta,kazu):
    if(keta<kazu):
        return 0
    result=1
    wari=1
    for i in range(kazu):
        wari*=i+1
        result*=keta-i
    result//=wari
    
    for i in range(kazu):
        result*=9
    return result


def Ans(moji,kazu):
    
    naga=len(moji)
    if(naga<kazu):
        return 0
    if(kazu==0):
        return 1
    sento=int(moji[0])
    if(naga==1):
        return sento
    
    if(sento==0):
        plus=Ans(moji[1:],kazu)
        return plus
    else:
        plus=Ans(moji[1:],kazu-1)
        
        return count(naga-1,kazu)+count(naga-1,kazu-1)*(sento-1)+plus

n=input()
l=len(n)
k=int(input())


print(Ans(n,k))

Solution (Python):
N, K = map(int, open(0).read().split())

X = str(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(X) + 1)]
dp[0][0][0] = 1

for i in range(len(X)):
    D = int(X[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else D) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k]

print(dp[-1][-1][-1] + int(X.count("0") == len(X) - K))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

L = list(str(N))
leng = len(L)
st = int(L[0])
cnt = 0


def keta(n,l):
    for i in range(l,leng):
        d = n[i]
        if d=='0':
            continue
        else:
            return (i,int(d))
    return -1,-1

if K==1:
    cnt += st
    cnt += 9*(leng-1)
elif K==2:
    i,d = keta(L,1)
    if not i==-1:
        cnt += d + 9*(leng-i-1)

    cnt += (st-1)*9*(leng-1) + 9*9*(leng-1)*(leng-2)//2
else:
    i_1,d_1 = keta(L,1)
    i_2,d_2 = keta(L,i_1+1)
    if not i_1==-1:
        a = (leng-i_1-1)
        cnt += (d_1-1)*9*a
        cnt += 9*9*(a*(a-1)//2)
    if not i_2==-1:
        cnt += d_2 + 9*(leng-i_2-1)
    cnt += (st-1)*9*9*(leng-1)*(leng-2)//2 + (9**3)*(leng-1)*(leng-2)*(leng-3)//6
print(cnt)

Solution (Python):
a = int(input())
b = int(input())
def aez(n, k):
    s = str(n)
    ln = len(s)-1
    n1 = int(s[0])
    if len(s) < k:
        return 0
    else:
        if k == 1:
            return 9 * ln + n1 
        elif k == 2:
            return (81 * ln * (ln-1) // 2) + aez(int('9'*ln), 1)*(n1-1) + aez(int(s[1:]), 1)
        else:
            return (729*ln*(ln-1)*(ln-2)//6) + aez(int('9'*ln), 2)*(n1-1) + aez(int(s[1:]), 2)
print(aez(a, b))

Solution (Python):
n = input()
k = int(input())

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    if l > 1:
        ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
        n = n[1:]
        while (n[0] == "0"):
            if (n == "0"):
                n = ""
                break
            
            n = n[1:]
        return ret + solve1(n)
    else:
        return 0

def solve3(n):
    l = len(n)
    if l > 2:
        ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
        n = n[1:]
        while (n[0] == "0"):
            
            if (n == "0"):
                n = ""
                break
            n = n[1:]
        return ret + solve2(n)
    else:
        return 0

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Solution (Python):
from operator import mul
from functools import reduce
from functools import lru_cache


def cmb(n, r):
    
    if n < 1 or r < 0:
        return 0
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


@lru_cache(maxsize=None)
def solve(N, k):
    if len(N) > 1 and N[0] == "0":
        return solve(N[1:], k)
    n = int(N)
    if k < 0:
        return 0
    elif len(N) < k:
        return 0
    elif n == 0:
        if k == 0:
            return 1
        elif k > 0:
            return 0
    elif n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1

    a = solve(N[1:], k - 1)
    b = (int(N[0]) - 1) * cmb(len(N) - 1, k - 1) * int(9**(k - 1))
    c = cmb(len(N) - 1, k) * int(9**k)
    
    return a + b + c


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

L = len(str(N))


print(solve(str(N), K))

Solution (Python):
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if m < K:
        return ans
    else:
        if K == 1:
            y = Z[0]
            ans += (m-1) * 9 + y
            
        elif K == 2:
            
            ans += ((m-1) * (m-2) // 2) * 9 * 9
            
            
            ans += (max(0,Z[0]-1)) * (m-1) * 9
            
            
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break            
            ans += nn(Z,K,m)
            
        elif K == 3:
            
            ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
            
            
            ans += (max(0,Z[0]-1)) * ((m-1) * (m-2) // 2) * 9 * 9
            
            
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break
            ans += nn(Z,K,m)
        return ans
if len(str(N)) < K:
    ans = 0
else:
    ans = nn(Z,K,m)        
print(ans)

Solution (Python):
from functools import lru_cache
import sys


def count(n):
    c = 0
    for s in str(n):
        if s != "0":
            c += 1
    return c


@lru_cache()
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)


def C(i, j):
    return fact(i) // (fact(j) * fact(i - j))


def calc(N, K):
    if K==0:
        return 1
    if N < 10000:
        retval = 0
        for i in range(N + 1):
            if count(i) == K:
                retval += 1
        return retval

    keta = len(str(N))
    retval = C(keta - 1, K) * (9**K)
    retval += calc(int(str(N)[1:]),K-1)
    retval += (int(str(N)[0])-1)*calc(10**(keta-1)-1,K-1)
    return retval



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

print(calc(N,K))

Solution (Python):
def main():
    N = input()
    len_N = len(N)
    K = int(input())
    dp = [[[0] * (K+5) for _ in range(2)] for _ in range(len_N + 5)]
    dp[0][0][0] = 1
    for i in range(1,len_N+1):
        for smaller in range(2):
            for k in range(K+1):
                if smaller == 0:
                    for x in range(int(N[i-1])+1):
                        if int(N[i-1]) == x:
                            if x == 0:
                                dp[i][smaller][k] += dp[i-1][smaller][k]
                            else:
                                dp[i][smaller][k+1] += dp[i-1][smaller][k]
                        else:
                            if x == 0:
                                dp[i][1][k] += dp[i-1][smaller][k]
                            else:
                                dp[i][1][k+1] += dp[i-1][smaller][k]
                else:
                    for x in range(10):
                        if x == 0:
                            dp[i][smaller][k] += dp[i-1][smaller][k]
                        else:
                            dp[i][smaller][k+1] += dp[i-1][smaller][k]


    print(dp[len_N][0][K] + dp[len_N][1][K])







if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
K = int(input())

l = len(str(N))
"""
print("N=",N)
print("K=",K)
print("l=",l,"桁")
"""


if K == 1:
    y = 9*(l-1)
    for i in range(1,10):
        p = i*10**(l-1)
        
        if p <= N:
            y += 1
        else:
            break
    print(y)
    
elif K == 2:
    
    
    y = 81*(l-1)*(l-2)//2
    
    
    
    for i in range(1,int(str(N)[0])+1):
        for j in range(1,10):
            for k in range(l-1):
                
                p = int(str(i)+"0"*k+str(j)+"0"*(l-2-k))
                if p <= N:
                    y += 1
                
    print(y)

else:
    
    
    y = 729*(l-1)*(l-2)*(l-3)//6
    
    
    
    top = int(str(N)[0])
    y += (top-1)*81*(l-1)*(l-2)//2
    
    
    for j in range(1,10):
        for k in range(1,10):
            for m in range(l-2):
                for n in range(l-2-m):
                    
                    p = int(str(top)+"0"*m+str(j)+"0"*n+str(k)+"0"*(l-3-m-n))
                    if p <= N:
                        y += 1
                    
    print(y)

Solution (Python):
def calc(n,k):
    while n[0] == '0' and len(n)>1:
        n=n[1:]
    
    digit = len(n)
    if digit < k:
        return 0
    
    comb = [1]*(k+1)
    for i in range(1,k+1):
        comb[i] = comb[i-1] * (digit-i) //i
    if k==1:
        return 9*comb[1] + int(n[0])
    elif k==2:
        return (9**2)*comb[2] + (int(n[0])-1) * 9*comb[1] + calc(n[1:],1)
    elif k==3:
        return (9**3)*comb[3] + (int(n[0])-1) * (9**2) * comb[2] + calc(n[1:],2)

n=input()
k=int(input())
print(calc(n,k))

Solution (Python):
N_str = str(input())
K = int(input())

digit_length = len(N_str)
topmost_digit = int(N_str[0])

C_table = [[0, 0, 0, 0] for _ in range(digit_length+10)]


def C(all, pick):
    if C_table[all][pick] == 0:
        count_child = 1
        count_parent = 1
        for i in range(pick):
            count_child *= all - i
            count_parent *= i + 1
        C_table[all][pick] = count_child // count_parent
    return C_table[all][pick]


def get_count(top_digit, digit_count, needed_nonzero):
    if needed_nonzero <= 0 or needed_nonzero > digit_count:
        return 0

    if digit_count == 1:
        if needed_nonzero == 1:
            return top_digit
        else:
            return 0

    if top_digit == 0:
        return get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero)

    if top_digit >= 1:
        count = C(digit_count - 1, needed_nonzero) * (9 ** needed_nonzero)
        if needed_nonzero == 1:
            count += 1

    if top_digit > 1:
        count += C(digit_count - 1, needed_nonzero - 1) * (9 ** (needed_nonzero - 1)) * (top_digit - 1)

    return count + get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero - 1)


print(get_count(topmost_digit, digit_length, K))

Solution (Python):
N = input()
K = int(input())

Nlen = len(N)

def func(N, K):
    Nlen = len(N)
    ans = 0
    if K == 1:
        ans += (Nlen - 1) * 9
        ans += int(N[0])
    if K == 2:
        for i in range(1, Nlen - 1):
            ans += 9 * 9 * i
        ans += (int(N[0]) - 1) * 9 * (Nlen - 1)
        for i in range(1, len(N)):
            if not N[i] == '0':
                ans += func(N[i:], 1)
                break
    if K == 3:
        for i in range(2, Nlen - 1):
            ans += 9 * 81 * i * (i - 1) // 2
        ans += (int(N[0]) - 1) * 81 * (Nlen - 1) * (Nlen - 2) // 2
        for i in range(1, len(N)):
            if not N[i] == '0':
                ans += func(N[i:], 2)
                break
    return ans
    
print(func(N, K))

Solution (Python):
N = list(map(int,input()))
K = int(input())
L = len(N)

def comb(n,k):
    if n < 0 or k < 0 or k > n:
        return 0
    ans = 1
    for i in range(k):
        ans *= n-i
    for i in range(k):
        ans //= i+1
    return ans

i = 0
D = [0] * K
M = K
for k in range(K):
    while i < L and N[i] == 0:
        i += 1
    if i < L:
        D[k] = i
        i += 1
    else:
        M = k
        break

ans = 0
for k in range(M):
    i = D[k]
    ans += comb(L-1-i,K-k)*(9**(K-k))
    ans += (N[i]-1) * comb(L-1-i,K-1-k)*(9**(K-1-k))
if K == M:
    ans += 1

print(ans)

Solution (Python):
import math
N = int(input())
l = len(str(N))
K = int(input())
def calc(a, b, c):
    t = 0
    if a-b-1>=0:
        t = (math.factorial(a-1) // (math.factorial(a-b-1) * math.factorial(b)))*(9**(b))
    if b==1:
        t2 = int(str(c)[0])
    else:
        t2 = (math.factorial(a-1) // (math.factorial(a-b) * math.factorial(b-1)))*(9**(b-1))*(int(str(c)[0])-1)
    t3 = 0
    try:
        n = int(str(c)[1:])
        if 2<=b<=len(str(n))+1:
            t3 = calc(len(str(n)), b-1, n)
    except:
        pass
    return t+t2+t3

if l>=K:
    print(calc(l, K, N))
else:
    print(0)

Solution (Python):
N = int(input())
K = int(input())

cmb = [[0]*(101) for _ in range(101)]
cmb[0][0] = 1
for i in range(1, 101):
    for j in range(i+1):
        if j == 0:
            cmb[i][j] = 1
            continue
        cmb[i][j] = cmb[i-1][j-1]+cmb[i-1][j]

S = str(N)
ans = 0
if K == len(S):
    for i in range(K):
        ans += (int(S[i])-1)*9**(K-i-1)
    ans += 1
else:
    for i in range(K, len(S)):
        ans += 9*cmb[i-1][K-1]*9**(K-1)
    if K == 1:
        ans += int(S[0])
    if K == 2:
        ans += (int(S[0])-1)*(len(S)-1)*9
        i = 1
        while i < len(S) and S[i] == "0":
            i += 1
        if i < len(S):
            ans += (len(S)-1-i)*9
            ans += int(S[i])
    if K == 3:
        ans += (int(S[0])-1)*cmb[len(S)-1][K-1]*9**(K-1)
        i = 1
        while i < len(S)-1 and S[i] == "0":
            i += 1
        flag = True
        if i < len(S)-1:
            ans += cmb[len(S)-i-1][2]*9**2
            ans += (int(S[i])-1)*(len(S)-i-1)*9
        else:
            flag = False
        i += 1
        while i < len(S) and S[i] == "0":
            i += 1
        if i < len(S) and flag:
            ans += (len(S)-i-1)*9
            ans += int(S[i])
print(ans)

Solution (Python):
n = int(input())
k = int(input())
import math
def k1(n):
    if n < 10:
        ans = n
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = 9 * (len(n1) - 1) + n2
    return int(ans)

def k2(n):
    if n < 100:
        ans = n - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (81 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 3)) / 2) +  (n2 - 1) * k1(10 ** (len(n1) - 1) - 1) + k1(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

def k3(n):
    if n < 1000:
        ans = n - k2(n) - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (729 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 4)) / 6) + (n2 - 1) * k2(10 ** (len(n1) - 1) - 1) + k2(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

if k == 1:
    print(k1(n))
elif k == 2:
    print(k2(n))
else:
    print(k3(n))

Solution (Python):
n = int(input())
k = int(input())



def choose(n, k):
    if k == 1:
        return n
    if k == 2:
        return n * (n-1) // 2
    if k == 3:
        return n * (n-1) * (n-2) // 6
    

def nonzerodigs(n):
    ss = list(map(int, list(str(n))))
    ss = [s for s in ss if s != 0]
    return len(ss)


def count(n, k):
    
    if k == 0:
        return 1

    if n < 1000:
        cnt = 0
        for i in range(1, n+1):
            if nonzerodigs(i) == k:
                cnt += 1

        return cnt

    ns = list(map(int, list(str(n))))
    d = len(ns)
    top3 = ns[0] * 100 + ns[1] * 10 + ns[2]
    cnt = 0
    for i in range(top3):
        nn = nonzerodigs(i)
        if nn > k:
            continue
        kk = k - nn
        if kk == 0:
            cnt += 1
        else:
            cnt += choose(d-3, kk) * (9**kk)

    nn = nonzerodigs(top3)
    if nn > k:
        return cnt
    elif nn == k:
        cnt += 1
        return cnt
    elif nn < k:
        kk = k - nn
        if kk > 2:
            print("ERROR")
            return -1
        nnn = int("".join(map(str, ns[3:])))
        return cnt + count(nnn, kk)

print(count(n,k))

Solution (Python):
def nCk(n, k):
  return factorial(n)/factorial(n-k)/factorial(k)

from math import factorial
N = input()
K = int(input())
order = len(N)
diff = order - K 
if order < K:
  print(0)
else:
  s = int(N[0])
  
  if order - 1 >= K:
    lower = nCk(order - 1, K) * (9**K)
  else:
    lower = 0
  total = lower
  for i in range(1, s):
  
    total += nCk(order - 1, K - 1) * (9**(K-1))

  if K == 1:
    total += 1
  elif K == 2:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(order - 1):
      for kk in range(1, 10):
        tmp = num[:k] + str(kk) + num[k+1:]
        if int(tmp) <= under:
          total += 1
  elif K == 3:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(1, order - 1):
      for j in range(k):
        for kk in range(1, 10):
          for jj in range(1, 10):
            tmp = num[:j] + str(jj) + num[j+1:k] +str(kk) +  num[k+1:]
            if int(tmp) <= under:
              total += 1


  print(int(total))

Solution (Python):
import numpy as np

def tmp(n,k):
    l = len(str(n))-1
    num = 0
    if(k == 1):
        num = 9 * l
        p = n // 10**l
        num += p
    elif(k == 2):
        for i in range(1,l):
            num += i * 81
        p = n // 10**l
        r = n % 10**l
        t = (n-r-1) % 10**(l)
        num += (p-1) * tmp(t,1) + tmp(r,1)
    elif(k == 3):
        for i in range(2,l):
            num += i * (i-1) / 2 * 729
        p = n // 10**l
        r = n % 10**l
        t = (n-r-1) % 10**(l)
        num += (p-1) * tmp(t,2) + tmp(r,2)
    return(num)



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


print(int(tmp(N,K)))

Solution (Python):
def comb(n,k):
  if k==0:
    return 1
  if k==1:
    return n
  if k==2:
    return n*(n-1)//2
  if k==3:
    return n*(n-1)*(n-2)//6
  return None
def cnt(n,k):
  if k==0:
    return 1
  if k>len(n):
    return 0
  return (comb(len(n)-1,k)*9**k
          +(int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
          +cnt(n[1:].lstrip('0'),k-1))
def main():
  n=input()
  k=int(input())
  print(cnt(n,k))
main()

Solution (Python):
def combination(n, k, mod=10**9+7):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % mod
    d = 1
    for x in range(1, k+1):
        d = (d * x) % mod
    comb *= pow(d, mod-2, mod)
    return comb % mod

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

x = [0] * 101
i = 0
NN = N
while NN > 0:
    x[i] = NN % 10
    NN = NN // 10
    i += 1

ans = 0
sum_non0 = 0
rK = K
for j in reversed(range(i)):
    if x[j] == 0:
        continue
    
    _ans = combination(j, rK) * (9 ** rK)
    
    if rK != 1:
        _ans += (x[j] - 1) * combination(j, rK-1) * (9 ** (rK - 1))
        
    else:
        _ans += x[j]
        

    ans += _ans
    rK -= 1
    if rK == 0:
        break

print(ans)

Solution (Python):
''' بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ '''

gi = lambda : list(map(int,input().split()))
s = input()
n, = gi()
ans = 0
mag = len(s) - 1

if len(s) <= 7:
	s = int(s)
	for k in range(s + 1):
		if len(str(k)) - str(k).count("0") == n:
			ans += 1
	print(ans)
	exit()
while mag - n >= 0:
	a = 9
	b = 1
	c = 1
	if n > 2:
		c = 81 * ((mag - 1) * (mag - 2) // 2)
	elif n > 1:
		b = 9 * (mag - 1)
	ans += a * b * c
	
	mag -= 1
mag = len(s)
a = int(s[0]) - 1
b, c = 1, 1
if n > 2:
	c = 81 * ((mag - 1) * (mag - 2) // 2)
elif n > 1:
	b = 9 * (mag - 1)
ans += a * b * c
a = b = c = 1
if n == 1:
	print(ans + 1)
	exit()
if n > 1:
	i = -1
	for k in range(1, len(s)):
		if s[k] != "0":
			i = k
			break;
	if i != -1:
		a = int(s[i]) - 1
		if n > 2:
			b = len(s) - i - 1
			b *= 9
		ans += a * b
		a = b = 1
		if n > 2:
			x = len(s) - i - 1
			a = 81 * (x * (x - 1)) // 2
		else:
			a = 9 * (len(s) - i - 1)
		ans += a
	if n > 2:
		a = b = c = 1
		j = -1
		for k in range(i + 1, len(s)):
			if s[k] != "0":
				j = k
				break;
		if j != -1:
			ans += 9 * (len(s) - j - 1) + int(s[j])
	else:
		ans += 1
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def rec(S, K):
    
    N = len(S)
    if N == 0 or K == 0 or N < K:
        return 0
    h = int(S[0])
    c = comb(N - 1, K - 1)
    ret = (9 - h) * c * (9 ** (K - 1))
    if S[0] == '0':
        ret += rec(S[1:], K)
    else:
        ret += rec(S[1:], K - 1)
    
    return ret

def solve(S: str, K: int):
    N = len(S)
    if N < K:
        print(0)
        return 0
    ret = comb(N, K) * (9 ** K)
    ret -= rec(S, K)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = str(next(tokens)) 
    K = int(next(tokens))  
    solve(N, K)

if __name__ == '__main__':
    main()