Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

t,a = src[0]
for ti,ai in src[1:]:
    tn = t + (ti - t%ti)%ti
    an = tn // ti * ai
    while an < a:
        tn += ti
        an += ai
    t,a = tn,an
print(t + a)


Fixed submission:
N = input()
rates = [tuple(map(int, raw_input().split())) for i in range(N)]

votes = rates[0]
for i in range(1,N):
    rate_t = rates[i][0]
    rate_a = rates[i][1]
    min_t = votes[0] / rate_t + (1 if votes[0] % rate_t > 0 else 0)
    min_a = votes[1] / rate_a + (1 if votes[1] % rate_a > 0 else 0)
    mag = max(min_t, min_a)
    votes = (rate_t * mag, rate_a * mag)

print sum(votes)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
src = list(map(int,input().split()))
ans = 0
for i,a in enumerate(src):
     l = r = 0
     for j in range(i-1,-1,-1):
         if src[j] < a: break
         l += 1
     for j in range(i+1,N):
         if src[j] < a: break
         r += 1
     ans += (l+1)*(r+1)*a
print(ans)

Fixed submission:
import heapq

N = int(input())
A = list(map(int,input().split()))

pos = [-1] * N
for i,a in enumerate(A):
    pos[a-1] = i

q = []
heapq.heapify(q)
right = [N] * N
for i,a in enumerate(A):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        right[v-1] = i
    heapq.heappush(q,-a)

q = []
heapq.heapify(q)
left = [0] * N
for i,a in reversed(list(enumerate(A))):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        left[v-1] = i+1
    heapq.heappush(q,-a)

ans = 0
for i,(p,l,r) in enumerate(zip(pos,left,right)):
    ans += (p-l+1) * (r-p) * (i+1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
src = list(map(int,input().split()))
ans = 0
for i,a in enumerate(src):
     l = r = 0
     for j in range(i-1,-1,-1):
         if src[j] < a: break
         l += 1
     for j in range(i+1,N):
         if src[j] < a: break
         r += 1
     ans += (l+1)*(r+1)*a
print(ans)

Fixed submission:
import heapq

N = int(input())
A = list(map(int,input().split()))

pos = [-1] * N
for i,a in enumerate(A):
    pos[a-1] = i

q = []
heapq.heapify(q)
right = [N] * N
for i,a in enumerate(A):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        right[v-1] = i
    heapq.heappush(q,-a)

q = []
heapq.heapify(q)
left = [0] * N
for i,a in reversed(list(enumerate(A))):
    while q and -q[0] > a:
        v = -heapq.heappop(q)
        left[v-1] = i+1
    heapq.heappush(q,-a)

ans = 0
for i,(p,l,r) in enumerate(zip(pos,left,right)):
    ans += (p-l+1) * (r-p) * (i+1)
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
k = int(input())
goal = ord('z') + 1
ans = []
for c in S:
    if c == 'a': continue
    d = goal - ord(c)
    if k >= d:
        k -= d
        ans.append('a')
    else:
        ans.append(c)
last = (k + ord(ans[-1]) - ord('a')) % 26
ans[-1] = chr(ord('a') + last)
print(''.join(ans))


Fixed submission:
S = input()
k = int(input())
goal = ord('z') + 1
ans = []
for c in S:
    if c == 'a':
        ans.append('a')
        continue
    d = goal - ord(c)
    if k >= d:
        k -= d
        ans.append('a')
    else:
        ans.append(c)
last = (k + ord(ans[-1]) - ord('a')) % 26
ans[-1] = chr(ord('a') + last)
print(''.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N,X = map(int,input().split())
A = list(map(int,input().split()))

INF = float('inf')
dp = [[INF]*N for i in range(N+1)]
dp[0] = A[:]

ans = sum(A)
for k in range(N):
    cost = k*X
    if cost > ans: break
    for i in range(N):
        dp[k+1][i] = min(dp[k][i], A[i-k])
    cost += sum(dp[k+1])
    ans = min(ans, cost)

print(ans)

Fixed submission:
N,X = map(int,input().split())
src = list(map(int,input().split()))
dp = src[:]
ans = float('inf')
for n in range(N):
    for m in range(N):
       if dp[m] > src[m-n]:
           dp[m] = src[m-n]
    ans = min(ans, sum(dp)+n*X)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def sub(a,b):
  return (a-b) % MOD

def mul(a,b):
  return ((a%MOD) * (b%MOD)) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

H,W,A,B = map(int,raw_input().split())

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[-1], n)
  factorical.append(f)
  factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans


Fixed submission:
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def mul(a,b):
  return (a*b) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

H,W,A,B = map(int,raw_input().split())

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[n-1], n)
  factorical.append(f)
  if(n <= max(H,W)):
    factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def sub(a,b):
  return (a-b) % MOD

def mul(a,b):
  return ((a%MOD) * (b%MOD)) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

factorical = [1]
factorical_inv = [1]
for n in range (1,200002):
  f = mul(factorical[-1], n)
  factorical.append(f)
  factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

H,W,A,B = map(int,raw_input().split())

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans

Fixed submission:
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def mul(a,b):
  return (a*b) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

H,W,A,B = map(int,raw_input().split())

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[n-1], n)
  factorical.append(f)
  if(n <= max(H,W)):
    factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
scale = 21
scale = 3
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1))
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,i,maxi)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Fixed submission:
n,k = map(int,input().split())
scale = 21
#scale = 4
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(rdb)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1))
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        for Z in range(X,Y):
          maxi = max(maxi,seg[db[i]+Z])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,rdb[i],maxi)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
n *= 2
ans = []
ans2 = []
for i in range(2,32*10**6):
  if n % i == 0:
    ans.append(i)
    n //= i
    cnt = 1
    while n % i == 0:
      n //= i
      cnt += 1
    ans2.append(cnt)
if n != 1:
  ans.append(n)
  ans2.append(1)
#print(ans)
#print(ans2)
l = len(ans)
for i in range(l):
  ans[i] **= ans2[i]
#print(ans)
time = [0 for _ in range(l)]
def nex(time):
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
can = []
while time != 'over':
  x = 1
  y = 1
  for i in range(l):
    if time[i] == 0:
      x *= ans[i]
    else:
      y *= ans[i]
  #print(x,y)
  X = int(x)
  Y = int(y)
  if x > y:
    rec = []
    while y != 1:
      rec.append(x//y)
      x,y = y,x%y
    #print(rec)
    if rec:
      le = len(rec)
      rec.reverse()
      now = [1,-rec[0]]
      for j in range(1,le):
        #print(now)
        now[0],now[1] = now[1],now[0]-now[1]*rec[j]
      #print(now)
      #print(min(abs(X*now[0]),abs(Y*now[1])))
      can.append(min(abs(X*now[0]),abs(Y*now[1])))
  time = nex(time)
print(min(can))

Fixed submission:
n = int(input())
n *= 2
ans = []
ans2 = []
for i in range(2,32*10**6):
  if n % i == 0:
    ans.append(i)
    n //= i
    cnt = 1
    while n % i == 0:
      n //= i
      cnt += 1
    ans2.append(cnt)
if n != 1:
  ans.append(n)
  ans2.append(1)
#print(ans)
#print(ans2)
l = len(ans)
for i in range(l):
  ans[i] **= ans2[i]
#print(ans)
if len(ans) == 1:
  print(ans[0]-1)
  exit()
time = [0 for _ in range(l)]
def nex(time):
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
can = []
while time != 'over':
  x = 1
  y = 1
  for i in range(l):
    if time[i] == 0:
      x *= ans[i]
    else:
      y *= ans[i]
  #print(x,y)
  X = int(x)
  Y = int(y)
  if x > y:
    rec = []
    while y != 1:
      rec.append(x//y)
      x,y = y,x%y
    #print(rec)
    if rec:
      le = len(rec)
      rec.reverse()
      now = [1,-rec[0]]
      for j in range(1,le):
        #print(now)
        now[0],now[1] = now[1],now[0]-now[1]*rec[j]
      #print(now)
      #print(min(abs(X*now[0]),abs(Y*now[1])))
      can.append(min(abs(X*now[0]),abs(Y*now[1])))
  time = nex(time)
print(min(can))
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
lr = []
for _ in range(k):
  lr.append(list(map(int,input().split())))
#print(lr)
imos = [0 for _ in range(n)]
imos[0] = 1
imos[1] = -1
now = 0
mod = 998244353
for i in range(n):
    now += imos[i]
    now %= mod
    #print(now)
    for j in range(k):
        try:
            imos[i+lr[j][0]] += now
            imos[i+lr[j][0]] %= mod
        except:
            pass
        try:
            imos[i+lr[j][1]+1] -= now
            imos[i+lr[j][1]+1] %= mod
        except:
            pass
    #print(imos)
print(now)

Fixed submission:
s = input()
if s[-1] == 's':
  print(s + 'es')
else:
  print(s + 's')
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b.reverse()
c = []
cs = -1
for i in range(n):
  if a[i] > b[i]:
    c.append(1)
  elif a[i] == b[i]:
    c.append(0)
    e = a[i]
    if cs == -1:
      cs = i
  else:
    c.append(-1)
#print(a)
#print(b)
#print(c)
ans = 0
for i in range(n):
  if a[i] == e:
    ans += 1
  if b[i] == e:
    ans += 1
if ans*2 > n:
  print('No')
else:
  print('Yes')
cnt = 0
for i in range(n):
  if cnt == ans:
    break
  if a[i] != e and b[i] != e:
    b[i],b[cs+cnt] = b[cs+cnt],b[i]
print(' '.join(map(str,b)))

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b.reverse()
c = []
cs = -1
e = -1
for i in range(n):
  if a[i] > b[i]:
    c.append(1)
  elif a[i] == b[i]:
    c.append(0)
    e = a[i]
    if cs == -1:
      cs = i
  else:
    c.append(-1)
#print(a)
#print(b)
#print(c)
ans = 0
db = 0
for i in range(n):
  if a[i] == e:
    ans += 1
  if b[i] == e:
    ans += 1
  if a[i] == b[i]:
    db += 1
if ans > n:
  print('No')
  exit()
print('Yes')
cnt = 0
#print(b)
#print(cs,db)
for i in range(n):
  if cnt == db:
    break
  #print(i,a[i],b[i])
  if a[i] != e and b[i] != e:
    b[i],b[cs+cnt] = b[cs+cnt],b[i]
    cnt += 1
    #print(b)
print(' '.join(map(str,b)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
for x in a:
  d = int(x)
  for y in range(2,10**3):
    if d % y == 0:
      p[y] += 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  #print(p)
if max(p) == 1:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while big % sml != 0:
    #print(big,sml)
    big,sml = sml,big%sml
  now = sml
  #print(now)
if now == 1:
  print('setwise coprime')
else:
  print('not coprime')
  #print(now)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
pr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
#print(pr)
at = 0
for x in a:
  d = int(x)
  for y in pr:
    if d % y == 0:
      if p[y] == 1:
        at = 1
      else:
        p[y] = 1
      while d % y == 0:
        d //= y
  if d != 1:
    if p[d] == 1:
      at = 1
    else:
      p[d] = 1
  if at == 1:
    break
  #print(p)
if at == 0:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while sml:
    #print(big,sml)
    big,sml = sml,big%sml
  now = big
  if now == 1:
    print('setwise coprime')
    exit()
  #print(now)
print('not coprime')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
l = len(s)
mod = 10**9 + 7
now = [0 for _ in range(l)]
now = [1] + now
for _ in range(n+l):
  last = now
  now = [0 for _ in range(l+1)]
  for i in range(l):
    now[i] += last[i] * 25
    now[i+1] = last[i]
  now[-1] += last[-1] * 26
  for i in range(l+1):
    now[i] %= mod
  #print(now)
print(now[-1])

Fixed submission:
n = int(input())
s = input()
l = len(s)
mod = 10**9 + 7

now = 1
for _ in range(n+l):
  now *= 25
  now %= mod
#print(now)
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    x -= mod % x
  return y
ans = 0
#print('#')
for i in range(n+l):
  now *= (n+l-i)
  now *= inv(i+1)
  now *= inv(25)
  now %= mod
  if i+1 >= l:
    ans += now
    ans %= mod
  #print(now)
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input())
print(int(a*b))

Fixed submission:
a,b = input().split()
a = int(a)
c,d = b.split('.')
c = int(c)
d = int(d)
print(a*c+a*d//100)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
t = ''
for i in range(n):
  if s[i] == 'P':
    t += 'P'
  else:
    t += 'D'
print(t)

Fixed submission:
s = input()
n = len(s)
t = ''
for i in range(n):
  if s[i] == 'P':
    t += 'P'
  else:
    t += 'D'
print(t)
Buggy python submission (verdict: Runtime Error):
mod = 10**9+7
n = int(input())
fish = {}
rish = {}
att = 0
for _ in range(n):
  a,b = map(int,input().split())
  if a*b != 0:
    try:
      fish[a/b] += 1
    except:
      fish[a/b] = 1
    rish[-b/a] = 1
  elif a == 0 and b == 0:
    att += 1
  elif a == 0:
    try:
      fish[0] = 1
    except:
      fish[0] = 1
    rish[10**20] = 1
  else:
    try:
      fish[10**20] = 1
    except:
      fish[10**20] = 1
    rish[0] = 1
#print(fish)
#print(rish)
double = [1]
for _ in range(3*10**5):
  double.append(double[-1]*2%mod)
ans = 1
for x in fish:
  if not fish[x]:
    #print('#',x)
    continue
  if x in rish:
    ans *= double[fish[x]] + double[fish[-1/x]] - 1
    ans %= mod
    fish[x] = 0
    fish[-1/x] = 0
  else:
    ans *= double[fish[x]]
    ans %= mod
  #print(ans)
ans = ans-1+att
ans %= mod
print(ans)

Fixed submission:
mod = 10**9+7
n = int(input())
inf = 10**20
fish = {}
rish = {}
att = 0
raw = []
raz = []
def lon(a,b,p):
  return p*10**40 + a*10**20 + b
def rev(z):
  p,a,b = z//(10**40),(z//(10**20))%(10**20),z%(10**20)
  return lon(b,a,1-p)
for _ in range(n):
  a,b = map(int,input().split())
  r = 1
  if a*b == 0:
    if a == b == 0:
      att += 1
    elif a == 0:
      raw.append(lon(0,1,1))
      raz.append(lon(1,0,0))
      fish[lon(0,1,1)] = [0,0]
      fish[lon(1,0,0)] = [0,0]
    else:
      raw.append(lon(1,0,0))
      raz.append(lon(0,1,1))
      fish[lon(1,0,0)] = [0,0]
      fish[lon(0,1,1)] = [0,0]
    continue
  if a*b < 0:
    r = 0
  a = abs(a)
  b = abs(b)
  big = int(a)
  sml = int(b)
  while sml != 0:
    big,sml = sml,big%sml
  a //= big
  b //= big
  raw.append(lon(a,b,r))
  raz.append(lon(b,a,1-r))
  fish[lon(a,b,r)] = [0,0]
  fish[lon(b,a,1-r)] = [0,0]
for x in raw:
  fish[x][0] += 1
for x in raz:
  fish[x][1] += 1
double = [1]
for _ in range(3*10**5):
  double.append(double[-1]*2%mod)
ans = 1
#print(fish)
for x in fish:
  re = rev(x)
  #print(x,fish[x][0],fish[x][1])
  #print(re)
  ans *= double[fish[x][0]] + double[fish[x][1]] - 1
  ans %= mod
  fish[x] = [0,0]
  fish[re] = [0,0]
ans -= 1
ans += att
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m,k = map(int,input().split())
mod = 998244353
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(2))
now = m
for _ in range(n-1):
  now *= m-1
  now %= mod
ans = int(now)
for i in range(k):
  now *= inv(m-1)
  now *= n-1-i
  now *= inv(i+1)
  now %= mod
  #print(now)
  ans += now
  ans %= mod
print(ans)

Fixed submission:
n,m,k = map(int,input().split())
mod = 998244353
if m == 1:
  if k == n-1:
    print(1)
  else:
    print(0)
  exit()
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(2))
now = int(m)
for _ in range(n-1):
  now *= m-1
  now %= mod
ans = int(now)
for i in range(k):
  now *= inv(m-1)
  now *= n-1-i
  now *= inv(i+1)
  now %= mod
  #print(now)
  ans += now
  ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
for i in range(l)[::-1]:
  now += (10**(l-1-i))*int(n[i])
  now %= 2019
  a[now] += 1
  #print(now)
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)

Fixed submission:
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
ten = [1]
for i in range(l-1):
  ten.append(ten[-1]*10%2019)
ten.reverse()
for i in range(l)[::-1]:
  now += ten[i]*int(n[i])
  now %= 2019
  a[now] += 1
  #print(now)
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(2500):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])

Fixed submission:
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(100):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
gcd = [[0 for _ in range(200)] for _ in range(200)]
for i in range(200):
  for j in range(200):
    big = i+1
    sml = j+1
    while sml != 0:
      big,sml = sml,big%sml
    gcd[i][j] = big
#print(gcd)
ans = 0
for a in range(n):
  for b in range(n):
    for c in range(n):
      x = gcd[a][b]
      y = gcd[a][c]
      ans += gcd[x-1][y-1]
      #print(a,b,c,x,y,gcd[x][y])
print(ans)

Fixed submission:
n = int(input())
gcd = [[0 for _ in range(200)] for _ in range(200)]
for i in range(200):
  for j in range(200):
    big = i+1
    sml = j+1
    while sml != 0:
      big,sml = sml,big%sml
    gcd[i][j] = big
#print(gcd)
ans = 0
for a in range(n):
  for b in range(n):
    for c in range(n):
      x = gcd[a][b]
      y = gcd[a][c]
      ans += gcd[x-1][y-1]
      #print(a,b,c,x,y,gcd[x][y])
print(ans)