Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = np.array([0]+[int(i) for i in readline().split()])
np.cumsum(a,out=a)
a = list(a)
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = np.array([0]+[int(i) for i in readline().split()])
np.cumsum(a,out=a)
  
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j-a >= t:
      break
    if j < a :
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,t = map(int,input().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,input().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    for k in range(j+1,n):
      if a[k] >= chk:
        ans += (k-j-1)
        break
      if k == n-1:
        ans += (n-j-1)
print(ans)  

Fixed submission:
import sys
input = sys.stdin.readline
import bisect
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    ind = bisect.bisect_left(a,chk)
    ans += (ind-j-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    for k in range(j+1,n):
      if a[k] >= chk:
        ans += (k-j-1)
        break
      if k == n-1:
        ans += (n-j-1)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
import bisect
n = int(input())
a = [int(i) for i in input().split()]
a = tuple(sorted(a))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    chk = a[i]+a[j]
    ind = bisect.bisect_left(a,chk)
    ans += (ind-j-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
g = [[]*(n*(n-1)//2) for _ in range(n*(n-1)//2)]
chk = set([])
cnt = 0
d = {}
st = set([])

for i in range(n):
  a = [int(i) for i in readline().split()]
  for j in range(n-2):
    A,b = min(a[j],i+1),max(a[j],i+1)
    p,q = min(a[j+1],i+1),max(a[j+1],i+1)    
    if not b*1000+A in chk:
      d[b*1000+A] = cnt
      cnt += 1
      chk.add(b*1000+A)
    if not q*1000+p in chk:
      d[q*1000+p] = cnt
      cnt += 1
      chk.add(q*1000+p)
    g[d[b*1000+A]].append(d[q*1000+p])
    if j == 0:
      st.add(d[b*1000+A])

# あとは頂点VのグラフをdfsしてLongest pathの長さを求める
# -1: unchecked, -2: checked and uncalculated
dp=[-1]*(n*(n-1)//2)
#flag=True
def dfs(v):
    #global flag
    dp[v]=-2
    length=0
    for nv in g[v]:
        if(dp[nv]==-2):
            print(-1)
            exit()
        if(dp[nv]==-1):
            dfs(nv)
        length=max(length,dp[nv]+1)
    dp[v]=length
            
st = list(st)
a = []
pp = 0
for i in st:dfs(i)
print(max(dp)+1)

Fixed submission:
import sys
sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
g = [[]*(n*(n-1)//2) for _ in range(n*(n-1)//2)]
chk = set([])
cnt = 0
d = {}
st = set([])

for i in range(n):
  a = [int(i) for i in readline().split()]
  for j in range(n-2):
    A,b = min(a[j],i+1),max(a[j],i+1)
    p,q = min(a[j+1],i+1),max(a[j+1],i+1)    
    if not b*1000+A in chk:
      d[b*1000+A] = cnt
      cnt += 1
      chk.add(b*1000+A)
    if not q*1000+p in chk:
      d[q*1000+p] = cnt
      cnt += 1
      chk.add(q*1000+p)
    g[d[b*1000+A]].append(d[q*1000+p])
    if j == 0:
      st.add(d[b*1000+A])

# あとは頂点VのグラフをdfsしてLongest pathの長さを求める
# -1: unchecked, -2: checked and uncalculated
dp=[-1]*(n*(n-1)//2)
#flag=True
def dfs(v):
    #global flag
    dp[v]=-2
    length=0
    for nv in g[v]:
        if(dp[nv]==-2):
            print(-1)
            exit()
        if(dp[nv]==-1):
            dfs(nv)
        length=max(length,dp[nv]+1)
    dp[v]=length
            
st = list(st)
a = []
pp = 0
for i in st:dfs(i)
print(max(dp)+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
import collections
chk = collections.deque([])
for i in range(n):
  s = input()
  s = sorted(s)
  chk.append(''.join(s))
#chk = list(chk)
c = collections.Counter(chk)
ans = 0
for i in range(len(c)):
  if c.most_common()[i][1] == 1:
    break
  else:
    ans += c.most_common()[i][1]*(c.most_common()[i][1]-1)//2
print(ans)

Fixed submission:
n = int(input())
import collections
chk = collections.deque([])
for i in range(n):
  s = input()
  s = sorted(s)
  chk.append(''.join(s))
#chk = list(chk)
c = collections.Counter(chk)
c = dict(c)
ans = 0
for i in c.values():
  ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))

from heapq import heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)

q = []
ans = 0
for i in range(1, m + 1):
    while chk and chk[-1][0] <= i:
        a,b = chk.pop()
        heappush(q,-b)
    if q:
        ans -= heappop(q)
print(ans)

Fixed submission:
from collections import deque
def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used
  
def belman(s,g,n,es):
    d = [10**10] * n
    d[s] = 0
    fin = False
    cnt = 0
    while True:
      update = False
      for p,q,r in es:
        if d[p] != 10**10 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True
      cnt += 1
      if not update:
        fin = True
        break
      if cnt > n+1:
          break      
    if fin:
        return max(0,-d[g])
    else:
        return -1   
  
n,m,p = map(int, input().split())

l = [[] for i in range(n)]
r = [[] for i in range(n)]
edges = []

for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    edges.append((a,b,-c+p))
    
use_nodes = use_path(n,0,l) & use_path(n,n-1,r)
es = [(a,b,c) for a,b,c in edges if a in use_nodes and b in use_nodes]
print(belman(0,n-1,n,es))
Buggy python submission (verdict: Runtime Error):
s = input().split()
if len(s) == 2:
  print(1,1)
  exit()
chk = [0]*len(s)
cntR = 1
r = 0
cntL = 0
for i in range(len(s)-1):
  if s[i] == 'R' and s[i+1] == 'L':
    r = i
    chk[r] += (cntR+1)//2
    chk[r+1] += (cntR)//2
    cntL = 1
  if s[i] == 'R' and s[i+1] == 'R':
    cntR += 1
  if s[i] == 'L' and s[i+1] == 'L':
    cntL += 1
  if s[i] == 'L' and s[i+1] == 'R':
    chk[r] += (cntL)//2
    chk[r+1] += (cntL+1)//2
    cntL = 0
    cntR = 1
chk[r] += (cntL)//2
chk[r+1] += (cntL+1)//2
chk = list(map(str,chk))
print(' '.join(chk))

Fixed submission:
s = input()
if len(s) == 2:
  print(1,1)
  exit()
chk = [0]*len(s)
cntR = 1
r = 0
cntL = 0
for i in range(len(s)-1):
  if s[i] == 'R' and s[i+1] == 'L':
    r = i
    chk[r] += (cntR+1)//2
    chk[r+1] += (cntR)//2
    cntL = 1
  if s[i] == 'R' and s[i+1] == 'R':
    cntR += 1
  if s[i] == 'L' and s[i+1] == 'L':
    cntL += 1
  if s[i] == 'L' and s[i+1] == 'R':
    chk[r] += (cntL)//2
    chk[r+1] += (cntL+1)//2
    cntL = 0
    cntR = 1
chk[r] += (cntL)//2
chk[r+1] += (cntL+1)//2
chk = list(map(str,chk))
print(' '.join(chk))

Buggy python submission (verdict: Runtime Error):
s = input().split()
if len(s) == 2:
  print(1,1)
  exit()
chk = [0]*len(s)
cntR = 1
r = 0
cntL = 0
for i in range(len(s)-1):
  if s[i] == 'R' and s[i+1] == 'L':
    r = i
    chk[r] += (cntR+1)//2
    chk[r+1] += (cntR)//2
    cntL = 1
  if s[i] == 'R' and s[i+1] == 'R':
    cntR += 1
  if s[i] == 'L' and s[i+1] == 'L':
    cntL += 1
  if s[i] == 'L' and s[i+1] == 'R':
    chk[r] += (cntL)//2
    chk[r+1] += (cntL+1)//2
    cntL = 0
    cntR = 1
chk[r] += (cntL)//2
chk[r+1] += (cntL+1)//2
chk = list(map(str,chk))
print(' '.join(chk))

Fixed submission:
s = input()
if len(s) == 2:
  print(1,1)
  exit()
chk = [0]*len(s)
cntR = 1
r = 0
cntL = 0
for i in range(len(s)-1):
  if s[i] == 'R' and s[i+1] == 'L':
    r = i
    chk[r] += (cntR+1)//2
    chk[r+1] += (cntR)//2
    cntL = 1
  if s[i] == 'R' and s[i+1] == 'R':
    cntR += 1
  if s[i] == 'L' and s[i+1] == 'L':
    cntL += 1
  if s[i] == 'L' and s[i+1] == 'R':
    chk[r] += (cntL)//2
    chk[r+1] += (cntL+1)//2
    cntL = 0
    cntR = 1
chk[r] += (cntL)//2
chk[r+1] += (cntL+1)//2
chk = list(map(str,chk))
print(' '.join(chk))
Buggy python submission (verdict: Runtime Error):
k = int(input())
X,Y = map(int,input().split())
x = abs(X)
y = abs(Y)

if k%2 == 0 and (x+y)%2 == 1:
  print(-1)
  exit()
  
import math
ans = []
m = math.ceil((x+y)/k)
if (x+y)/k == int((x+y)/k):
  for i in range(m):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
    
elif m == 1:
  if (x+y)%2 == 1:
    ans.append(x,x-k)
    ans.append(x+(k+x-y)//2,(-k+x+y)//2)
    ans.append(x,y)
  else:
    ans.append(-k+(x+y)//2,(x+y)//2)
    ans.append(x,y)
    
elif (m*k-x-y)%2 == 0:
  x += (m*k-x-y)//2
  for i in range(m-1):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
  ans.append((abs(X),y))
  
elif (m*k-x-y)%2 == 1:
  x += (m*k-x-y)//2
  m += 1
  for i in range(m-1):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
  ans.append((abs(X),y))
  
print(len(ans))
for i,j in ans:
  if X < 0:
    i *= -1
  if Y < 0:
    j *= -1
  print(i,j)

Fixed submission:
k = int(input())
X,Y = map(int,input().split())
x = max(abs(X),abs(Y))
y = min(abs(X),abs(Y))
c = (k-(x+y)%k)%k
if k%2 == 0 and (x+y)%2 == 1:
  print(-1)
  exit()
  
import math
ans = []
m = math.ceil((x+y)/k)
if (x+y)/k == int((x+y)/k):
  for i in range(m):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
    
elif m == 1:
  if (x+y)%2 == 1:
    ans.append((x,x-k))
    ans.append((x+(k+x-y)//2,(-k+x+y)//2))
    ans.append((x,y))
  else:
    ans.append(((x+y)//2,-k+(x+y)//2))
    ans.append((x,y))
               
elif c%2 == 0 and x+y >= k:
  a = abs((k*m-x-y)//2)
  for i in range(m-1):
    l = k*i+k
    if a >= l:
      ans.append((0,-l))
    elif a < l <= x+a:
      ans.append((l-a,-a))
    elif x+a < l:
      ans.append((x,l-x-2*a))
  ans.append((x,y))
  
else:
  m += 1
  a = abs((k*m-x-y)//2)
  for i in range(m-1):
    l = k*i+k
    if a >= l:
      ans.append((0,-1))
    elif a < l <= x+a:
      ans.append((l-a,-a))
    elif x+a < l:
      ans.append((x,l-x-2*a))
  ans.append((x,y))
  
print(len(ans))
for i,j in ans:
  if abs(X) < abs(Y):
    i,j = j,i
  if X < 0:
    i *= -1
  if Y < 0:
    j *= -1
  print(i,j)
Buggy python submission (verdict: Runtime Error):
from colletions import Counter
n = int(input())
if n%3 != 0:
  print('No')
else:
  a = [int(i) for i in input().split()]
  c = Counter(a)
  for i in c.values():
    if i != n//3:
      print('No')
      exit()
  print('Yes')

Fixed submission:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
s = set(a)
c = Counter(a)

if n%3 != 0:
  if s == {0}:
    print('Yes')
  else:
    print('No')
else:
  if len(c) > 3:
      print('No')
  elif len(c) == 3:
    a,b,q = list(s)
    if a^b == q and c[a] == n//3 and c[b] == c[q]:
      print('Yes')
    else:
      print('No')
  elif len(c) == 2:
    if not 0 in s:
      print('No')
    else:
      if c[0] == n//3:
        print('Yes')
      else:
        print('No')
  elif len(c) == 1:
    if s == {0}:
      print('Yes')
    else:
      print('No')
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())

if k > (n-1)*(n-2)//2:
  print(-1)
  exit()
    
m = (n-1)*(n-2)//2+(n-1)-k
print(m)
for i in range(n-1):
  print(1,2+i)
    
if m > n-1:
  c = m-(n-1)
  for i in range(1,n-1):
    if c == 0:
        break
    for j in range(2,n-i+1):
      print(j,j+i)
      cnt -= 1
      if c == 0:
        break

Fixed submission:
n,k = map(int,input().split())
if n == 2 and k == 0:
  print(1)
  print(1,2)
  exit()
  
if k > (n-1)*(n-2)//2 or n == 2:
  print(-1)
  exit()
  
if n == 3:
  if k == 1:
    print(2)
    print(1,2)
    print(2,3)
  elif k == 0:
    print(3)
    print(1,2)
    print(2,3)
    print(3,1)
  else:
    print(-1)
  exit()
    
m = (n-1)*(n-2)//2+(n-1)-k
print(m)
for i in range(n-1):
  print(1,2+i)
for i in range(min(n-1,m-n+1)):
  if 3+i > n:
    print(2+i,2)
  else:
    print(2+i,3+i)
    
if m > (n-1)*2:
  cnt = m-(n-1)*2
  for i in range(2,n-2):
    if cnt == 0:
        break
    for j in range(2,n-i+1):
      print(j,j+i)
      cnt -= 1
      if cnt == 0:
        break
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[n][m])

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[n][m])
Buggy python submission (verdict: Time Limit Exceeded):
l = input()
mod = 10**9+7
L = len(l)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def f(x):
  res = 0
  for i in range(x+1):
    res += pow(2,x-i,mod)*comb(x,i,mod)%mod
    res %= mod
  return res
  
ans = f(L)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= f(L-1-i)*pow(2,cnt+1,mod)%mod
    ans %= mod
  else:
    cnt += 1
    
print(ans%mod)

Fixed submission:
l = input()
mod = 10**9+7
L = len(l)

ans = pow(3,L,mod)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= pow(3,L-1-i,mod)*pow(2,cnt+1,mod)
    ans %= mod
  else:
    cnt += 1
    
print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
l = input()
mod = 10**9+7
L = len(l)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def f(x):
  res = 0
  for i in range(x+1):
    res += pow(2,x-i,mod)*comb(x,i,mod)%mod
  return res
  
ans = f(L)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= f(L-1-i)*pow(2,cnt+1,mod)
  else:
    cnt += 1
    
print(ans%mod)

Fixed submission:
l = input()
mod = 10**9+7
L = len(l)

ans = pow(3,L,mod)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= pow(3,L-1-i,mod)*pow(2,cnt+1,mod)
    ans %= mod
  else:
    cnt += 1
    
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
c = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    c.append((x, s, t))
kkk.sort()
d = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in k:
    ss = bisect_left(d, s - x)
    tt = bisect_left(d, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print(*ans,sep='\n')

Fixed submission:
import sys
from bisect import bisect_left

n,q = map(int, input().split())
lines = sys.stdin.readlines()
c = []
for line in lines[:n]:
    s,t,x = map(int, line.split())
    c.append((x,s,t))
c.sort()
d = list(map(int,lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x,s,t in c:
    ss = bisect_left(d,s-x)
    tt = bisect_left(d,t-x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print(*ans,sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
x,y,z,k = map(int,readline().split())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
c = [int(i) for i in readline().split()]
from bisect import bisect_left,insort
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

stop = 0
ans = []
cn = 0
for i in a:
  for j in b:
    for l in c:
      if i+j+l <= stop:
        break
      if cn >= k:
        if bisect_left(ans,i+j+l) > 0:
          insort(ans,i+j+l)
        else:
          stop = i+j+l
      else:
        insort(ans,i+j+l)
        cn += 1
        
ans = ans[::-1]
for i in ans[:k]:
  print(i)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
x,y,z,k = map(int,readline().split())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
c = [int(i) for i in readline().split()]
from heapq import heappush,heappop,heapify
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

chk = [(-(a[0]+b[0]+c[0]),0,0,0)]
heapify(chk)
C = set((0,0,0))
ans = []
for i in range(k):
  p,q,r,s = heappop(chk)
  ans.append(-p)
  if not (q+1,r,s) in C and q < x-1:
    C.add((q+1,r,s))
    heappush(chk,(-(a[q+1]+b[r]+c[s]),q+1,r,s))
  if not (q,r+1,s) in C and r < y-1:
    C.add((q,r+1,s))
    heappush(chk,(-(a[q]+b[r+1]+c[s]),q,r+1,s))
  if not (q,r,s+1) in C and s < z-1:
    C.add((q,r,s+1))
    heappush(chk,(-(a[q]+b[r]+c[s+1]),q,r,s+1))
    
for i in ans:
  print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
mod = 10**9+7
if n == 3:
  print(61)
  exit()
  
st = ['AGC','GAC','ACG','AGTC','AGGC','ATGC']
from collections import deque
st = deque(st)
l = 3
cnt = 0
e = n-3

while st:
  if cnt == l:
    st = set(st)
    l = len(st)
    cnt = 0
    e -= 1
    st = deque(st)
  j = st.popleft()
  if e == 0:
    a = l%mod
    break
  else:
    st.append('A'+j)
    st.append('G'+j)
    st.append('C'+j)
    st.append('T'+j)
    st.append(j+'A')
    st.append(j+'C')
    st.append(j+'G')
    st.append(j+'T')
  cnt += 1
  
print(pow(4,n,mod)-a)

Fixed submission:
n = int(input())
mod = 10**9+7
  
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] #AGC
  dp[i][1] -= dp[i-2][2] #GAC
  dp[i][1] -= dp[i-3][0]*3 #AGTC,AGGC,ATGC
  dp[i][2] -= dp[i-2][0] #ACG
  dp[i][2] += dp[i-3][2] #GACG
  
print(sum(dp[n-1])%mod)