Buggy python submission (verdict: Runtime Error):
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else 1
print(X[int(input())][1])

Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Buggy python submission (verdict: Time Limit Exceeded):
s=input();n=len(s)
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;z=f(i,t,k)
 if a:
  if k==1:z=a+(n-i)*9
  else:z=f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,t,k-1)
 return z
print(f(0,0,int(input())))

Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Buggy python submission (verdict: Time Limit Exceeded):
s=input();n=len(s)
def f(i,t,k):
 if k>n-i:return 0
 if k==0:return 1
 a=max(t,int(s[i]));i+=1;z=f(i,t,k)
 if a:z=f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,t,k-1)
 return z
print(f(0,0,int(input())))

Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Buggy python submission (verdict: Runtime Error):
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
 z=0
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))


Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Buggy python submission (verdict: Runtime Error):
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
z=0
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))


Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Buggy python submission (verdict: Runtime Error):
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  z=0
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

Fixed submission:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))