Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

graph=[set() for _ in range(N+1)]
for _ in range(M):
  A,B=map(int,input().split())
  graph[A].add(B)
#print(graph)

visited=[False]*(N+1)
def dfs(path):
  u=path[-1]
  visited[u]=True
  for v in graph[u]:
    if visited[v]:
      if path[0]==v:
        cycle_list.append(path+[v])
    else:
      dfs(path+[v])
  visited[u]=False

cycle_list=[]
for i in range(1,N+1):
  dfs([i])
  
#print(cycle_list)
for cycle in cycle_list:
  #print(cycle)
  cycle_set=set(cycle)
  for c in cycle:
    edge_subs=set()
    if len(cycle_set&graph[c])>1:
      break
  else:
    print(len(cycle)-1)
    for i in range(len(cycle)-1):
      print(cycle[i])
    break
else:
  print(-1)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

graph=[set() for _ in range(N+1)]
for _ in range(M):
  A,B=map(int,input().split())
  graph[A].add(B)
#print(graph)

visited=[False]*(N+1)
def dfs(path):
  global cycle
  u=path[-1]
  
  visited[u]=True  
  for v in graph[u]:
    if visited[v]:
      cycle=list(path+[v])
      return
    else:
      dfs(path+[v])      
    if cycle:
      return    
  visited[u]=False
  
cycle=[]
for i in range(1,N+1):
  dfs([i])
  if cycle:
    break
else:
  print(-1)
  sys.exit(0)
    
#remove prefix  
for i in range(len(cycle)):
  if cycle[i]==cycle[-1]:
    cycle=cycle[i:]
    break
#print(cycle)

cycle_set=set(cycle)
subgraph=[set() for _ in range(N+1)]
for c in cycle_set:
  for v in graph[c]:
    if v in cycle_set:
      subgraph[c].add(v)
#print(subgraph)    

#visited=[False]*(N+1)
ex_path=[]
def dfs2(path,t):
  global ex_path
  u=path[-1]
  if u==t:
    ex_path=path
    return
  
  for v in graph[u]:
    dfs2(path+[v],t)
    if ex_path:
      return

graph=subgraph
while True:
  for i in range(len(cycle)-1):
    u=cycle[i]
    v=cycle[i+1]
    w=-1
    if len(graph[u])>1:
      for x in graph[u]:
        if x!=v:
          w=x
          break
      break
  else:
    print(len(cycle)-1)
    for i in range(len(cycle)-1):
      print(cycle[i])
    sys.exit(0)
    
  #print(u,v,w)
  #w->u
  dfs2([w],u)
  cycle=ex_path+[w]
  #print(cycle)
  cycle_set=set(cycle)
  subgraph=[set() for _ in range(N+1)]
  for c in cycle_set:
    for v in graph[c]:
      if v in cycle_set:
        subgraph[c].add(v)
        
  graph=subgraph
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

while(M>0):
  alist[0]//=2
  if alist[0]<alist[1]:
    alist.sort(reverse=True)
  M-=1

print(sum(alist))


Fixed submission:
#from heapq import heappush, heappop
import heapq

N,M=map(int,input().split())
alist=list(map(int,input().split()))

hq=[]
for a in alist:
  heapq.heappush(hq,-a)
  
while(M>0):
  target=-1*heapq.heappop(hq)
  target//=2
  heapq.heappush(hq,-target)
  M-=1

answer_list=[heapq.heappop(hq) for i in range(len(hq))]
#print(answer_list)
print(-sum(answer_list))

Buggy python submission (verdict: Time Limit Exceeded):
import math

N,M=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

alog0=math.log2(alist[0])
alist_log=[]
diff_list=[]
for i in range(N):
  a=alist[i]
  alogi=math.log2(a)  
  alist_log.append(alogi)

#print(alist)
#print(alist_log)

tlist=[0]*N
while(M>0):
  max_value=max(alist_log)
  max_index=alist_log.index(max_value)
  
  alist_log[max_index]-=1
  tlist[max_index]+=1
  M-=1
#print(tlist)

answer=0
for i in range(N):
  answer+=alist[i]//(2**tlist[i])

print(answer)

Fixed submission:
#from heapq import heappush, heappop
import heapq

N,M=map(int,input().split())
alist=list(map(int,input().split()))

hq=[]
for a in alist:
  heapq.heappush(hq,-a)
  
while(M>0):
  target=-1*heapq.heappop(hq)
  target//=2
  heapq.heappush(hq,-target)
  M-=1

answer_list=[heapq.heappop(hq) for i in range(len(hq))]
#print(answer_list)
print(-sum(answer_list))
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
S=input()

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
    
for i in range(K):
  ch_list=ch_list[2:]
  
#print(ch_list)
print(N-1-len(ch_list))

Fixed submission:
N,K=map(int,input().split())
S=input()

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
#print(ch_list)
len_ch=len(ch_list)

if len_ch>=2*K:
  print(N-1-len_ch+2*K)
elif len_ch==2*K-1:
  print(N-1-len_ch+2*K-1)
else:
  print(N-1)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
S=input()

def calc_n(SS):
  cnt=0
  if SS[0]=='R' and SS[1]=='R':
    cnt+=1
  for i in range(1,N-1):
    if SS[i]=='L' and SS[i-1]=='L':
      cnt+=1
    elif SS[i]=='R' and SS[i+1]=='R':
      cnt+=1
  if SS[-1]=='L' and SS[-2]=='L':
    cnt+=1  
  return cnt
  
new_queue=[S]
cnt=0

while(True):  
  cnt+=1
  queue=new_queue[:]

  for q in queue:
    for l in range(N):
      for r in range(l,N):
        new_S = q[0:l]
        for k in range(l,r+1):
          if q[r+l-k]=='L':
            new_S += 'R'
          else:
            new_S += 'L'
        new_S += q[r+1:N]
        new_queue.append(new_S)
        
  if cnt>=K:
    break
    
#print(new_queue)
answer=-1
answer_arg=""
for q in new_queue:
  if calc_n(q)>answer:
    answer=calc_n(q)
    answer_arg=q
    
print(answer)
#print(answer_arg)

Fixed submission:
N,K=map(int,input().split())
S=input()

ch_list=[]
for i in range(1,N):
  if S[i-1]!=S[i]:
    ch_list.append(i)
#print(ch_list)
len_ch=len(ch_list)

if len_ch>=2*K:
  print(N-1-len_ch+2*K)
elif len_ch==2*K-1:
  print(N-1-len_ch+2*K-1)
else:
  print(N-1)
Buggy python submission (verdict: Time Limit Exceeded):
p=int(input())
alist=list(map(int,input().split()))

fact_list=[1]
fact_inv_list=[1]
for i in range(1,p):
  fact=(fact_list[-1]*i)%p
  fact_list.append(fact)
  fact_inv_list.append(pow(fact,p-2,p))
def comb_mod(n,r):
  return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  
answer_list=[0]*p
for i in range(p):
  a=alist[i]
  if a==1:
    #1-(x-i)^(p-1)
    coeff_list=[0]*p
    coeff_list[0]=1
    for j in range(p):
      coeff=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      coeff_list[j]-=coeff
      coeff_list[j]%=p
      
    #print(i,coeff_list)
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      answer_list[i]%=p
      
print(*answer_list)

Fixed submission:
p=int(input())
alist=list(map(int,input().split()))

fact_list=[1]
fact_inv_list=[1]
for i in range(1,p):
  fact=(fact_list[-1]*i)%p
  fact_list.append(fact)
  fact_inv_list.append(pow(fact,p-2,p))
def comb_mod(n,r):
  return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  
answer_list=[0]*p
for i in range(p):
  a=alist[i]
  if a==1:
    #1-(x-i)^(p-1)
    coeff_list=[0]*p
    coeff_list[0]=1
    for j in range(p):
      coeff=comb_mod(p-1,j)*pow(-i,p-1-j,p)
      coeff_list[j]-=coeff
      coeff_list[j]%=p
      
    #print(i,coeff_list)
    for i in range(p):
      answer_list[i]+=coeff_list[i]
      answer_list[i]%=p
      
print(*answer_list)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
alist=list(map(int,input().split()))

sum_a=sum(alist)
alist.sort()
#print(sum_a,alist)

#M=1の場合にも対応
divisor_set=set()
for i in range(1,int(sum_a**0.5)+1):
  if sum_a%i==0:
    divisor_set.add(i)
    divisor_set.add(sum_a//i)
divisor_list=list(divisor_set)
divisor_list.sort()
#print(divisor_list)

answer=0
for d in divisor_list:
  rlist=[]
  for a in alist:
    rlist.append((a%d,(d-a%d)%d))
  rlist.sort()
  
  r1list,r2list=[],[]
  for r1,r2 in rlist:
    r1list.append(r1)
    r2list.append(r2)  
  #print(d,r1list,r2list)
  
  for i in range(len(rlist)):
    r1sum=sum(r1list[:i])
    r2sum=sum(r2list[i:])
    if r1sum==r2sum and r1sum<=K:
      answer=d
      break
      
print(answer)

Fixed submission:
N,K=map(int,input().split())
alist=list(map(int,input().split()))

sum_a=sum(alist)
alist.sort()
#print(sum_a,alist)

#M=1の場合にも対応
divisor_set=set()
for i in range(1,int(sum_a**0.5)+1):
  if sum_a%i==0:
    divisor_set.add(i)
    divisor_set.add(sum_a//i)
divisor_list=list(divisor_set)
divisor_list.sort()
#print(divisor_list)

answer=0
for d in divisor_list:
  rlist=[]
  for a in alist:
    rlist.append((a%d,(d-a%d)%d))
  rlist.sort()
  
  r1list,r2list=[],[]
  for r1,r2 in rlist:
    r1list.append(r1)
    r2list.append(r2)  
  #print(d,r1list,r2list)
  
  for i in range(len(rlist)):
    r1sum=sum(r1list[:i])
    r2sum=sum(r2list[i:])
    if r1sum==r2sum and r1sum<=K:
      answer=d
      break
      
print(answer)
Buggy python submission (verdict: Runtime Error):
K=int(input())
X,Y=map(int,input().split())

ispos_X,ispos_Y=True,True
if X<0:
  X=-X
  ispos_X=False
if Y<0:
  Y=-Y
  ispos_Y=False

if K%2==0 and (X+Y)%2==1:
  print(-1)
else:
  xx,yy=0,0
  vec_list=[]
  if K%2==0:
    while((X-xx)+(Y-yy)>2*K):
      if X-xx>K:
        xx+=K
        vec_list.append((K,0))
      elif Y-yy>K:
        yy+=K
        vec_list.append((0,K))
        
    #print(xx,yy,vec_list)
    diff_x=X-xx
    diff_y=Y-yy
    if diff_x+diff_y==K:
      vec_list.append((diff_x,diff_y))
    else:
      buf=2*K-diff_x-diff_y    
      vec_list.append((diff_x+buf//2,K-diff_x-buf//2))
      vec_list.append((-buf//2,K-buf//2))
      
  else:
    while((X-xx)+(Y-yy)>2*K):
      if X-xx>K:
        xx+=K
        vec_list.append((K,0))
      elif Y-yy>K:
        yy+=K
        vec_list.append((0,K))    
        
    #print(xx,yy,vec_list)
    diff_x=X-xx
    diff_y=Y-yy
    if diff_x+diff_y==K:
      vec_list.append((diff_x,diff_y))
    elif (diff_x+diff_y)%2==0:      
      buf=2*K-diff_x-diff_y
      if diff_x<K:
        vec_list.append((diff_x+buf//2,K-diff_x-buf//2))
        vec_list.append((-buf//2,K-buf//2))
      else:
        vec_list.append((K-diff_y-buf//2,diff_y+buf//2))
        vec_list.append((K-buf//2,-buf//2))
    elif diff_x+diff_y<K:
      xx+=diff_x
      yy+=-K+diff_x
      vec_list.append((diff_x,-K+diff_x))
      
      diff_x=X-xx
      diff_y=Y-yy      
      buf=2*K-diff_x-diff_y
      vec_list.append((diff_x+buf//2,K-diff_x-buf//2))
      vec_list.append((-buf//2,K-buf//2))
    else:
      if diff_x<K:
        xx+=diff_x
        yy+=K-diff_x
        vec_list.append((diff_x,K-diff_x))
      elif diff_y<K:
        xx+=K-diff_y
        yy+=diff_y        
        vec_list.append((K-diff_y,diff_y))

      diff_x=X-xx
      diff_y=Y-yy      
      buf=2*K-diff_x-diff_y
      vec_list.append((diff_x+buf//2,K-diff_x-buf//2))
      vec_list.append((-buf//2,K-buf//2))

  #print(vec_list)
  print(len(vec_list))
  pos_x,pos_y=0,0
  for x,y in vec_list:
    if ispos_X:
      pos_x+=x
    else:
      pos_x-=x
    if ispos_Y:
      pos_y+=y
    else:
      pos_y-=y
      
    print(pos_x,pos_y)

Fixed submission:
A,B=map(int,input().split())
if (A+B)%2==0:
  print((A+B)//2)
else:
  print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7
S=input()

dp=[]
for i in range(len(S)+1):
  dp.append([0]*13)
dp[0][0]=1
#print(dp)

for i in range(1,len(S)+1):
  if S[i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[i][(10*k+j)%13]+=dp[i-1][k]
        dp[i][(10*k+j)%13]%=MOD
  else:
    si=int(S[i-1])
    for k in range(13):
      dp[i][(10*k+si)%13]+=dp[i-1][k]
      dp[i][(10*k+si)%13]%=MOD
    
#print(dp)
print(dp[-1][5])

Fixed submission:
mod=10**9+7

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)
#print(dp)

if S[-1]=="?":
  for j in range(10):
    dp[-1][j]=1
else:
  sj=int(S[-1])
  dp[-1][sj]=1
  
pow_mod=1
for i in range(1,len(S)):
  pow_mod*=10
  pow_mod%=13
  if S[-i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[-i-1][(k+j*pow_mod)%13]+=dp[-i][k]
        dp[-i-1][(k+j*pow_mod)%13]%=mod
  else:
    sj=int(S[-i-1])
    for k in range(13):
      dp[-i-1][(k+sj*pow_mod)%13]+=dp[-i][k]
      dp[-i-1][(k+sj*pow_mod)%13]%=mod
    
#print(dp)
print(dp[0][5]%mod)

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

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)
#print(dp)

if S[-1]=="?":
  for j in range(10):
    dp[-1][j]=1
else:
  sj=int(S[-1])
  dp[-1][sj]=1
  
pow_mod=1
for i in range(1,len(S)):
  pow_mod*=10
  pow_mod%=13
  if S[-i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[-i-1][(k+j*pow_mod)%13]+=dp[-i][k]
        dp[-i-1][(k+j*pow_mod)%13]%=mod
  else:
    sj=int(S[-i-1])
    for k in range(13):
      dp[-i-1][(k+sj*pow_mod)%13]+=dp[-i][k]
      dp[-i-1][(k+sj*pow_mod)%13]%=mod
    
#print(dp)
print(dp[0][5]%mod)

Fixed submission:
mod=10**9+7

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)
#print(dp)

if S[-1]=="?":
  for j in range(10):
    dp[-1][j]=1
else:
  sj=int(S[-1])
  dp[-1][sj]=1
  
pow_mod=1
for i in range(1,len(S)):
  pow_mod*=10
  pow_mod%=13
  if S[-i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[-i-1][(k+j*pow_mod)%13]+=dp[-i][k]
        dp[-i-1][(k+j*pow_mod)%13]%=mod
  else:
    sj=int(S[-i-1])
    for k in range(13):
      dp[-i-1][(k+sj*pow_mod)%13]+=dp[-i][k]
      dp[-i-1][(k+sj*pow_mod)%13]%=mod
    
#print(dp)
print(dp[0][5]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
alist=[0]+list(map(int,input().split()))

blist=[0]*(N+1)
for i in reversed(range(1,N+1)):
  blist[i]^=alist[i]
  for j in range(2,N+1):
    if i%j==0:
      blist[i//j]^=blist[i]
    
#print(blist)
answer=sum(blist)
print(answer)
if answer>0:
  print(" ".join(["1"]*answer))

Fixed submission:
N=int(input())
alist=[0]+list(map(int,input().split()))
#print(alist)

blist=[0]*(N+1)
for i in reversed(range(1,N+1)):
  blist[i]=alist[i]
  for j in range(2*i,N+1,i):
    blist[i]+=blist[j]
  blist[i]%=2
  
#print(blist[1:])
answer_list=[i for i in range(1,N+1) if blist[i]==1]
print(len(answer_list))
print(*answer_list)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N=int(input())
alist=list(map(int,input().split()))
arr=np.array(alist)

matrix=[]
for i in range(N-1):
  array=[0]*i + [1/2,1/2] + [0]*(N-i-2)
  matrix.append(array)
matrix.append([1/2]+[0]*(N-2)+[1/2])

#print(matrix)
mat = np.matrix(matrix)
#print(mat)
mat_rev=mat**-1
#print(mat_rev)

prod=np.dot(mat_rev,arr)
prod_list=prod.tolist()

prod_list_int=[]
for p in prod_list[0]:
  prod_list_int.append(str(int(p)))
  
#print(prod_list_int)
print(" ".join(prod_list_int))

Fixed submission:
N=int(input())
alist=list(map(int,input().split()))

asum=sum(alist)
ans_list=[-1]*N

minus_even=sum(alist[1:N:2])
minus_odd=sum(alist[2:N:2])

for i in range(N//2):
  ans_list[2*i] = asum-2*minus_even
  ans_list[2*i+1] = asum-2*minus_odd
  
  minus_even += alist[(2*i+N)%N]-alist[(2*i+1)%N]
  minus_odd += alist[(2*i+N+1)%N]-alist[(2*i+2)%N]
  
ans_list[-1]=asum-2*minus_even
  
ans_list_str=map(str,ans_list)  
print(" ".join(ans_list_str))
Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp,dp_sum=[],[]
for i in range(N+1):
  dp.append([0]*(M+1))
  dp_sum.append([1]*(M+1))
dp[0][0]=1
#print(dp)

for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      dp[i][j]=dp_sum[i-1][j-1]      
    dp_sum[i][j]=(dp[i][j]+dp_sum[i-1][j]+dp_sum[i][j-1]-dp_sum[i-1][j-1])%MOD
#print(dp)
#print(dp_sum)

print(dp_sum[-1][-1])

Fixed submission:
MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp,dp_sum=[],[]
for i in range(N+1):
  dp.append([0]*(M+1))
  dp_sum.append([1]*(M+1))
dp[0][0]=1
#print(dp)

for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      dp[i][j]=dp_sum[i-1][j-1]      
    dp_sum[i][j]=(dp[i][j]+dp_sum[i-1][j]+dp_sum[i][j-1]-dp_sum[i-1][j-1])%MOD
#print(dp)
#print(dp_sum)

print(dp_sum[-1][-1])

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

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp=[]
for i in range(N+1):
  dp.append([0]*(M+1))
dp[0][0]=1
#print(dp)

answer=1
for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      for ii in range(i):
        for jj in range(j):
          dp[i][j]+=dp[ii][jj]
          answer+=dp[ii][jj]
          answer%=MOD

#print(dp)
print(answer)

Fixed submission:
MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp,dp_sum=[],[]
for i in range(N+1):
  dp.append([0]*(M+1))
  dp_sum.append([1]*(M+1))
dp[0][0]=1
#print(dp)

for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      dp[i][j]=dp_sum[i-1][j-1]      
    dp_sum[i][j]=(dp[i][j]+dp_sum[i-1][j]+dp_sum[i][j-1]-dp_sum[i-1][j-1])%MOD
#print(dp)
#print(dp_sum)

print(dp_sum[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
L=input()

sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    sum += cnt_2*(3**(len(L)-i-1))
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)

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

m3=1
m3_list=[]
for i in range(len(L)):
  m3_list.append(m3)
  m3 = (3*m3)%mod                   
m3_list.reverse()
  
sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    #sum += cnt_2*(3**(len(L)-i-1))
    sum += cnt_2*m3_list[i]
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)

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

sum=0
cnt=0
for i in range(len(L)):  
  if L[i] == "1":
    sum += (2**cnt)*(3**(len(L)-i-1))
    sum %= mod
    cnt += 1
    
sum += 2**cnt
sum %= mod
print(sum)

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

m3=1
m3_list=[]
for i in range(len(L)):
  m3_list.append(m3)
  m3 = (3*m3)%mod                   
m3_list.reverse()
  
sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    #sum += cnt_2*(3**(len(L)-i-1))
    sum += cnt_2*m3_list[i]
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)

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

sum=0
cnt=0
for i in range(len(L)):  
  if L[i] == "1":
    sum += (2**cnt)*(3**(len(L)-i-1))
    sum %= mod
    cnt += 1
    
sum += 2**cnt
sum %= mod
print(sum)

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

m3=1
m3_list=[]
for i in range(len(L)):
  m3_list.append(m3)
  m3 = (3*m3)%mod                   
m3_list.reverse()
  
sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    #sum += cnt_2*(3**(len(L)-i-1))
    sum += cnt_2*m3_list[i]
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  while(bl.find("AD")!=-1):
    answer+=bl.count("AD")
    bl=bl.replace("AD","DA")
    
print(answer)

Fixed submission:
s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()

cnt=0
while(True):
  if s.find("ABC") == -1:
    break
  else:
    cnt += s.count("ABC")
    s = s.replace("ABC","BCA")
    
print(cnt)

Fixed submission:
s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()

cnt=0
while(True):
  if s.find("ABC") == -1:
    break
  else:
    s = s.replace("ABC","BCA",1)
    cnt += 1
    
print(cnt)

Fixed submission:
s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
Q=int(input())

alist=[]
b=0
for _ in range(Q):
  query=list(map(int,input().split()))
  if len(query)==3:
    dummy,ai,bi=query
    alist.append(ai)
    alist.sort()
    b+=bi
  else:
    minarg=alist[(len(alist)-1)//2]
    minvalue=b
    for i in range(len(alist)):
      minvalue+=abs(alist[i]-minarg)
    print(minarg,minvalue)

Fixed submission:
import heapq
Q=int(input())

alist=[]
hq_left,hq_right=[],[]
dummy,a1,b1=map(int,input().split())
heapq.heappush(hq_left,-a1)
heapq.heappush(hq_right,a1)
b=b1

min_arg=-hq_left[0]
min_diff=0
#min_value=b      
for _ in range(Q-1):
  query=list(map(int,input().split()))
  if len(query)==3:    
    dummy,ai,bi=query
    b+=bi
    
    max_left=-hq_left[0]
    min_right=hq_right[0]
    if ai<max_left:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_left,-ai)
      heapq.heappop(hq_left)
      heapq.heappush(hq_right,max_left)      
      min_diff+=max_left-ai
    elif min_right<ai:
      heapq.heappush(hq_right,ai)
      heapq.heappush(hq_right,ai)
      heapq.heappop(hq_right)
      heapq.heappush(hq_left,-min_right)      
      min_diff+=ai-min_right
    else:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_right,ai)      
  else:    
    min_arg=-hq_left[0]
    min_value=min_diff+b
    print(min_arg,min_value)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions

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

max_gcd = 1
for skip in range(N):
  first = True
  for i,an in enumerate(alist):
    if i == skip:
      continue
    elif first:
      gcd = an
      first = False
      
    gcd = fractions.gcd(gcd,an)
    if gcd < max_gcd:
      break
    
  if max_gcd < gcd:
    max_gcd = gcd
    
print(max_gcd)

Fixed submission:
import fractions

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

gcd_left_list = [0]*N
gcd = alist[0]
for i in range(1,N):
  gcd = fractions.gcd(gcd,alist[i-1])
  gcd_left_list[i] = gcd

gcd_right_list = [0]*N
gcd = alist[N-1]
for i in reversed(range(0,N-1)):
  gcd = fractions.gcd(gcd,alist[i+1])
  gcd_right_list[i] = gcd

#print(alist)
#print(gcd_left_list)
#print(gcd_right_list)
    
max_gcd = max(gcd_right_list[0], gcd_left_list[N-1])
for i in range(1,N-1):
  gcd = fractions.gcd(gcd_left_list[i],gcd_right_list[i])
  if gcd > max_gcd:
    max_gcd = gcd

print(max_gcd)
Buggy python submission (verdict: Runtime Error):
N=input()
alist = list(map(int,input().split()))

ans = 0
for i in range(N):
  ans += abs(alist[i])
  
print(ans)

Fixed submission:
N = int(input())
alist = list(map(int,input().split()))

neg_cnt = 0
abs_min = 999999999999999
for an in alist:
  if an < 0:
    neg_cnt += 1
  if abs_min > abs(an):
    abs_min = abs(an)
 
ans = 0
for i in range(N):
  ans += abs(alist[i])
  
if neg_cnt%2 == 0:
  print(ans)
else:
  print(ans-2*abs_min)