Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
ans_bigger = max(a)
ans_half = a / 2
dif = float("inf")
for i in range(n):
  x = abs(a[i]-ans_half)
  if dif > x:
    dif = x
    ans_smaller = a[i]
print(ans_bigger,ans_smaller)

Fixed submission:
n = int(input())
a = sorted(list(map(int,input().split())))
ans_bigger = max(a)
ans_half = ans_bigger / 2
dif = float("inf")
for i in range(n-1):
  x = abs(a[i]-ans_half)
  if dif > x:
    dif = x
    ans_smaller = a[i]
print(ans_bigger,ans_smaller)
Buggy python submission (verdict: Runtime Error):
s = input()
s_list = list(s)
s_list[3] = "8"
print("",join(s_list))

Fixed submission:
s = input()
s_list = list(s)
s_list[3] = "8"
print("".join(s_list))
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter
n,h = map(int,input().split())
ab = []
ans = 0
a = 0
for i in range(n):
  ab.append(list(map(int,input.split())))
ab.sort()
swing = ab.pop(-1)
ab = sorted(a,key = itemgetter(1))
ab.reverse
for i in range(len(ab)):
  h -= ab[i][1]
  ans += 1
  if h <= 0:
    print(ans)
    a += 1
    break
if a == 0:
  if h%swing[1] == 0:
    h -= swing[1]
    ans += h // swing[1]
    print(ans+1)
  else:
    h -= swing[1]
    ans += h // swing[1]
    print(ans+2)


Fixed submission:
N,H = map(int,input().split());
ab = [list(map(int,input().split())) for _ in range(N)]
ab.sort(key = lambda x:x[0],reverse = True)
swing = ab[0][0]
ans = 0
if H<= ab[0][1]:
    print(1)
else:
    ab.sort(key = lambda x:x[1],reverse = True)
    for i in range(N):
        if ab[i][1] >= swing:
          H -= ab[i][1]
          ans += 1 
        else:
            continue
        if H <= 0:
            break
    else:
        if H % swing == 0:
            ans += H//swing
        else:
            ans += H//swing +1
    print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
def dfs(i,f,sum):
  if i == 3:
    if sum == 7:
      print(f + "=7")
      exit()
  dfs(i+1,f + "+" + s[i+1],sum+int(s[i+1]))
  dfs(i+1,f + "-" + s[i+1],sum-int(s[i+1]))
dfs(0,s[0],int(s[0]))

Fixed submission:
s = input()
def dfs(i,f,sum):
  if i == 3:
    if sum == 7:
      print(f + "=7")
      exit()
  else:
    dfs(i+1,f + "+" + s[i+1],sum+int(s[i+1]))
    dfs(i+1,f + "-" + s[i+1],sum-int(s[i+1]))
dfs(0,s[0],int(s[0]))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
neo_b = [[] for _ in range(n)]
ans = 0
for i in range(n):
  neo_b[i] = bisect.bisect_left(a,b[i])
for i in range(n):
  ans += sum(neo_b[:bisect.bisect_left(b,c[i])])
print(ans)

Fixed submission:
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(n):
  ans += bisect.bisect_left(a,b[i])*(n-bisect.bisect_right(c,b[i]))
print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input())
t = list(input())
s_copy = s
ans_list = []
n = len(s)
m = len(t)
flag = 0
flag_2 = 0
for i in range(n):
  if s[i] == "?" or s[i] == t[flag]:
    if flag == m-1:
      flag_2 = 1
      for j in range(flag,-1,-1):
        s[i-(m-1-j)] = t[j]
      ans_list.append(s)
      s = s_copy
    else:
      flag += 1
  else:
    flag = 0
x = len(ans_list)
if flag_2 == 1:
  for l in range(x):
    for k in range(n):
      if s[l][k] == "?":
        s[l][k] = "a"
  ans_list.sort()
  print("".join(ans_list[0]))
else:
  print("UNRESTORABLE")

Fixed submission:
import copy
s = list(input())
t = list(input())
ans_list = []
n = len(s)
m = len(t)
for i in range(n-m+1):
  s_copy = copy.copy(s)
  judgement = True
  for j in range(m):
    if s_copy[i+j] != "?" and s_copy[i+j] != t[j]:
      judgement = False
      break
    else:
      s_copy[i+j] = t[j]
  if judgement:
    ans_list.append(s_copy)
x = len(ans_list)
if ans_list != []:
  for l in range(x):
    for k in range(n):
      if ans_list[l][k] == "?":
        ans_list[l][k] = "a"
  ans_list.sort()
  print("".join(ans_list[0]))
else:
  print("UNRESTORABLE")

Buggy python submission (verdict: Runtime Error):
s = list(input())
t = list(input())
n = len(s)
m = len(t)
flag = 0
flag_2 = 0
for i in range(n):
  if s[i] == "?" or s[i] == t[flag]:
    if flag == m-1:
      flag_2 = 1
      for j in range(flag,-1,-1):
        s[i-(m-1-j)] = t[j]
      break
    else:
      flag += 1
  else:
    flag = 0
if n<m:
  flag_2 = 0
if flag_2 == 1:
  for k in range(n):
    if s[k] == "?":
      s[k] = "a"
  print("".join(s))
else:

Fixed submission:
import copy
s = list(input())
t = list(input())
ans_list = []
n = len(s)
m = len(t)
for i in range(n-m+1):
  s_copy = copy.copy(s)
  judgement = True
  for j in range(m):
    if s_copy[i+j] != "?" and s_copy[i+j] != t[j]:
      judgement = False
      break
    else:
      s_copy[i+j] = t[j]
  if judgement:
    ans_list.append(s_copy)
x = len(ans_list)
if ans_list != []:
  for l in range(x):
    for k in range(n):
      if ans_list[l][k] == "?":
        ans_list[l][k] = "a"
  ans_list.sort()
  print("".join(ans_list[0]))
else:
  print("UNRESTORABLE")
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = sorted(list(map(int,input().split())),reverse = True)
use = []
flag = -1
for i in range(n):
  if flag == a[i]:
    use.append(a[i])
    flag = -1
  else:
    flag = a[i]
if len(use)<2:
  print(0)
else:
  use.sort(reverese =True)
  print(use[0]*use*[2])

Fixed submission:
n = int(input())
a = sorted(list(map(int,input().split())),reverse = True)
use = []
flag = -1
for i in range(n):
  if flag == a[i]:
    use.append(a[i])
    flag = -1
  else:
    flag = a[i]
if len(use)<2:
  print(0)
else:
  use.sort(reverse =True)
  print(use[0]*use[1])
Buggy python submission (verdict: Runtime Error):
import functions
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())))
a_max = max(a)
a_gcd = a[0]
for i in range(n):
  a_gcd = functions.gcd(a_gcd,a[i])
if k <= a_max and k % a_gcd == 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Fixed submission:
import fractions
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())))
a_max = max(a)
a_gcd = a[0]
for i in range(n):
  a_gcd = fractions.gcd(a_gcd,a[i])
if k <= a_max and k % a_gcd == 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append(str(a[i]))
  b.reverse()
print(" ".join(b))

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
left = []
right = []
for i in range(n):
  right.append(str(a[i]))
  left,right = right,left
left.reverse()
print(" ".join(left+right))
Buggy python submission (verdict: Runtime Error):
def sign(x):
  if x<0:
    return -1
  elif x>0:
    return 1
  else:
    retrun 0
n = int(input())
a = list(map(int,input().split()))
cumulative_sum = a[0]
flag = sign(cumulative_sum)
ans = 0
for i in range(1,n):
  cumulative_sum += a[i]
  if sign(cumulative_sum) == flag or sign(cumulative_sum) == 0:
    ans += abs(-flag - cumulative_sum)
  flag = sign(cumulative_sum)
print(ans)

Fixed submission:
def sign(x):
  if x<0:
    return -1
  elif x>0:
    return 1
  else:
    return 0
n = int(input())
a = list(map(int,input().split()))
a_sum_pn = 0
a_sum_np = 0
ans_pn = 0
ans_np = 0
flag = 1
for i in range(n):
  a_sum_pn += a[i]
  a_sum_np += a[i]
  if sign(a_sum_pn) != flag:
    ans_pn += abs(flag-a_sum_pn)
    a_sum_pn = flag
  if sign(a_sum_np) != -flag:
    ans_np += abs(-flag-a_sum_np)
    a_sum_np = -flag
  flag *= -1
print(min(ans_pn,ans_np))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=sorted(list(map(int,input().split())))
flag=0
ans=1
a_cumulative=[0]
for i in range(n):
  flag+=a[i]
  a_cumulative.append(flag)
a.reverse()
a_cumulative.reverse()
for j in range(n-1):
  if a[j]＜= a_cumulative[j+1]*2:
    ans+=1
print(ans)

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())))
flag=0
ans=1
a_cumulative=[0]
for i in range(n):
  flag+=a[i]
  a_cumulative.append(flag)
a.reverse()
a_cumulative.reverse()
for j in range(n-1):
  if a[j] <= a_cumulative[j+1]*2:
    ans+=1
  else:
    break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,x = map(int,input().split())
ans = 0
for i in range(a,b+1):
  if i % x == 0:
    ans += 1
  else:
    continue
print(ans)

Fixed submission:
a,b,x = map(int,input().split())
print(b//x-(a-1)//x)
Buggy python submission (verdict: Time Limit Exceeded):
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
    flag = min(a[:i+1])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

Fixed submission:
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

Buggy python submission (verdict: Time Limit Exceeded):
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = max(a)
flag_2 = a.index(flag)
for i in range(n):
  if i <= flag_2:
    ans[i] = flag-a[i]
  else:
    flag = max(a[i:n])
    flag_2 = a.index(flag)
    ans[i] = flag-a[i]
print(ans.count(max(ans)))

Fixed submission:
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

Buggy python submission (verdict: Time Limit Exceeded):
import array
n,t = map(int,input().split())
a = list(map(int,input().split()))
a = array.array("i",a)
ans = []
flag = max(a)
flag_2 = a.index(flag)
for i in range(n):
  if i <= flag_2:
    ans.append(flag-a[i])
  else:
    flag = max(a[i:n])
    flag_2 = a.index(flag)
    ans.append(flag-a[i])
print(ans.count(max(ans)))

Fixed submission:
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

Buggy python submission (verdict: Time Limit Exceeded):
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = []
flag = max(a)
flag_2 = a.index(flag)
for i in range(n):
  if i <= flag_2:
    ans.append(flag-a[i])
  else:
    flag = max(a[i:n])
    flag_2 = a.index(flag)
    ans.append(flag-a[i])
print(ans.count(max(ans)))

Fixed submission:
n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))
Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)
ans = 0
for i in range(n):
  if s[i] == "g" and flag == 0:
    flag+=1
  elif s[i] == "g" and flag != 0:
    flag -= 1
    ans += 1
  elif s[i] == "p" and flag == 0:
    flag += 1
    ans -= 1
  else:
    flag -= 1
print(ans)
    
    

Fixed submission:
s = list(input())
n = len(s)
ans = 0
flag = 0
for i in range(n):
  if s[i] == "g" and flag == 0:
    flag+=1
  elif s[i] == "g" and flag != 0:
    flag -= 1
    ans += 1
  elif s[i] == "p" and flag == 0:
    flag += 1
    ans -= 1
  else:
    flag -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)
def dfs(i,f):
  if i == n:
    return sum(list(map(int,f.split("+"))))
  return dfs(i + 1, f + s[i + 1]) + \
           dfs(i + 1, f + "+" + s[i + 1])
print(dfs(0,0))

Fixed submission:
s = list(input())
n = len(s)-1
def dfs(x,y):
  ans = 0
  if x == n:
    return sum(list(map(int,"".join(y).split("+"))))
  else:
    return dfs(x+1,y+"+"+s[x+1])+dfs(x+1,y+s[x+1])
print(dfs(0,s[0]))
Buggy python submission (verdict: Runtime Error):
n,a = map(int,input().split())
x = list(map(int,input().split()))
max_x = max(x)
dp = [[[0]*(n*max_x+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
  for j in range(n+1):
    for k in range(n*max_x+1):
      if i>=1 and k < x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]
      elif i>=1 and j>= 1 and k>= x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
      else:
        continue
ans = 0
for j in range(1,n+1):
  ans += dp[n][j][j*a]
print(ans)

Fixed submission:
n,a = map(int,input().split())
x = list(map(int,input().split()))
max_x = max(x)
dp = [[[0]*(n*max_x+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
  for j in range(n+1):
    for k in range(n*max_x+1):
      if i>=1 and k < x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]
      elif i>=1 and j>= 1 and k>= x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
      else:
        continue
ans = 0
for j in range(1,n+1):
  if j*a <= n*max_x+1:
    ans += dp[n][j][j*a]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,a = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  y = []
  item = 0
  for j in range(n):
    if ((i >> j) & 1):
      y.append(x[j])
      item += 1
  if item != 0 and sum(y) == item*a:
    ans += 1
print(ans)

Fixed submission:
n,a = map(int,input().split())
x = list(map(int,input().split()))
max_x = max(x)
dp = [[[0]*(n*max_x+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
  for j in range(n+1):
    for k in range(n*max_x+1):
      if i>=1 and k < x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]
      elif i>=1 and j>= 1 and k>= x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
      else:
        continue
ans = 0
for j in range(1,n+1):
  if j*a <= n*max_x+1:
    ans += dp[n][j][j*a]
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
s = list(str(input()))
ans = deque()
for i in s:
  if i == "B":
    if ans == []:
      continue
    else:
      ans.pop()
  else:
    ans.append(i)
print("".join(ans))

Fixed submission:
from collections import deque
s = list(str(input()))
ans = deque()
for i in s:
  if i == "B":
    if ans == deque([]):
      continue
    else:
      ans.pop()
  else:
    ans.append(i)
print("".join(ans))

Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)
ans = []
for i in range(n):
  if i == "B":
    if ans == []:
      continue
    else:
      ans.remove(ans[-1])
  else:
    ans.appned(i)
print("".join(ans))

Fixed submission:
from collections import deque
s = list(str(input()))
ans = deque()
for i in s:
  if i == "B":
    if ans == deque([]):
      continue
    else:
      ans.pop()
  else:
    ans.append(i)
print("".join(ans))

Buggy python submission (verdict: Runtime Error):
s = list(map(str,input().split()))
n = len(s)
ans = []
for i in range(n):
  if i == "B":
    if ans == []:
      continue
    else:
      ans.remove(ans[-1])
  else:
    ans.appned(i)
print("".join(ans))

Fixed submission:
from collections import deque
s = list(str(input()))
ans = deque()
for i in s:
  if i == "B":
    if ans == deque([]):
      continue
    else:
      ans.pop()
  else:
    ans.append(i)
print("".join(ans))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
s = input()
s_con = Counter(s)
mode = s_con.most_common(1)
s_com = mode[0][1]
s_con_str = mode[0][0]
s_rev = s.reverse()
if s_com >= (len(s) / 2):
  print("-1 -1")
else:
  ans_1 = s.find(s_con_str)
  ans_2 = s_rev.find(s_con_str)
  print(str(ans_1) + " " +str(ans_2))

Fixed submission:
s = list(input())
n = len(s)
ans_1 = -1
ans_2 = -1
if n == 2:
  if s[0] == s[1]:
    ans_1 = 1
    ans_2 = 2
else:
  for i in range(n-2):
    if s[i] == s[i+1]:
      ans_1 = i+1
      ans_2 = i+2
      break
    elif s[i] == s[i+2]:
      ans_1 = i+1
      ans_2 = i+3
      break
print(ans_1,ans_2)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
D = set(map(int,input().split()))
ans = N
while(True):
  if any(i in D for i in list(map(str,ans))):
    ans += 1
  else:
    print(ans)
    break

Fixed submission:
N,K = map(int,input().split())
D = set(map(int,input().split()))
ans = N
while(True):
  if any([i in D for i in list(map(int,str(ans)))]):
    ans += 1
  else:
    print(ans)
    break
Buggy python submission (verdict: Time Limit Exceeded):
import math
k = int(input())
 
 
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)

Fixed submission:
from math import gcd
k = int(input())
 
 
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, gcd(b, c))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
k = int(input())


ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)

Fixed submission:
from math import gcd
k = int(input())
 
 
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, gcd(b, c))
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K= [int(i) for i in input().split()]
An = [int(i) for i in input().split()]

i = 0
checked = [0 for _ in range(N)]
c = 0
while checked[i] == 0:
  c += 1
  checked[i] = c
  i = An[i] - 1
if checked[i] >= K:
  i = 0
  for k in range(mod_K):
    i = An[i] - 1
  print(i + 1)
else:
  period = c - checked[i] + 1
  diff = K - checked[i] + 1
  mod_diff = diff % period
  for k in range(mod_diff):
    i = An[i] - 1
  print(i + 1)
  

Fixed submission:
N, K= [int(i) for i in input().split()]
An = [int(i) for i in input().split()]

i = 0
checked = [0 for _ in range(N)]
c = 0
while checked[i] == 0:
  c += 1
  checked[i] = c
  i = An[i] - 1
if checked[i] >= K:
  i = 0
  for k in range(K):
    i = An[i] - 1
  print(i + 1)
else:
  period = c - checked[i] + 1
  diff = K - checked[i] + 1
  mod_diff = diff % period
  for k in range(mod_diff):
    i = An[i] - 1
  print(i + 1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H, W = [int(i) for i in input().split()]
Shw = [[0 if i =="." else 1 for i in input()] for _ in range(H)]

changes = [[-1 for _ in range(W)] for _ in range(H)]
que = deque()
i0 = 0
j0 = 0
que.append((i0, j0,  0, 0))

while len(que) > 0:
  i, j,  o, c = que.popleft()
  current = Shw[j][i]
  diff = 1 if current > 0 and o == 0 else 0
  change = c + diff
  if changes[j][i] == -1:
    changes[j][i] = change
  else:
    changes[j][i] = min(change, changes[j][i])
  if i < W-1:
    que.append((i+1, j, current, change))
  if j < H-1:
    que.append((i, j+1, current, change))
print(changes[-1][-1])
    


Fixed submission:
from collections import deque
H, W = [int(i) for i in input().split()]
Shw = [[0 if i =="." else 1 for i in input()] for _ in range(H)]

changes = [[-1 for _ in range(W)] for _ in range(H)]

for j in range(H):
  for i in range(W):
    current = Shw[j][i]
    if i == 0 and j ==0:
      changes[j][i] = current
    elif i == 0:
      changes[j][i] = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
    elif j == 0:
      changes[j][i] = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
    else:
      upper = changes[j-1][i] + (1 if current == 1 and Shw[j-1][i] == 0 else 0)
      lower = changes[j][i-1] + (1 if current == 1 and Shw[j][i-1] == 0 else 0)
      changes[j][i] = min(upper, lower)
      
print(changes[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, P = [int(i) for i in input().split()]
S = input()

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
#    ui = int(S[i-1:])
    number = number + int(S[i-1])*10**(N-i)
    mp = number % P
    Pa[mp] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)
  


Fixed submission:
N, P = [int(i) for i in input().split()]
S = input()


def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
    number = (number + int(S[i-1])*mod_pow(10, N - i, P)) % P
    Pa[number] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = [int(i) for i in input().split()]
S = input()

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  for i in range(N, 0, -1):
    ui = int(S[i-1:])
    mp = ui % P
    Pa[mp] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)
  


Fixed submission:
N, P = [int(i) for i in input().split()]
S = input()


def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
    number = (number + int(S[i-1])*mod_pow(10, N - i, P)) % P
    Pa[number] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)
Buggy python submission (verdict: Runtime Error):
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)

s = int(N[0])
#lower  = factorial(order-1)/factorial(diff-1)/ factorial(K) * (9**K)
if order - 1 >= K:
  lower = nCk(order - 1, K) * (9**K)
else:
  lower = 0
total = lower
for i in range(1, s):
#  total += factorial(order-1)/factorial(diff)/ factorial(K-1) * (9**(K-1))
  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))
#pattern = factorial(order)/factorial(diff)/ factorial(K) * (9**K)






Fixed submission:
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])
  #lower  = factorial(order-1)/factorial(diff-1)/ factorial(K) * (9**K)
  if order - 1 >= K:
    lower = nCk(order - 1, K) * (9**K)
  else:
    lower = 0
  total = lower
  for i in range(1, s):
  #  total += factorial(order-1)/factorial(diff)/ factorial(K-1) * (9**(K-1))
    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))
  #pattern = factorial(order)/factorial(diff)/ factorial(K) * (9**K)