Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#gが目標点数
d,g=map(int,input().split())

cnt=10*1000+1
numberOfMondai=0
KindOfMondai = {}
kindOfMondaiBin=""
zero=""

for i in range(1,d+1):
    c,p=map(int,input().split())
    if c>1:
        for j in range(c):
            KindOfMondai[zero+"0"*(c-j-1)+"1"+"0"*(j)]=i*100
    else:
        KindOfMondai[zero+"1"]=i*100
    kindOfMondaiBin=zero+"1"*c
    zero=zero+"0"*c
    KindOfMondai[kindOfMondaiBin]=p
    numberOfMondai+=c

KindOfMondaiZero={}
for key in KindOfMondai.keys():
    KindOfMondaiZero[int(key+"0"*(numberOfMondai-len(key)),2)]=KindOfMondai[key]

#print(KindOfMondaiZero)

number=10**9
for i in range(2**numberOfMondai):
    point=0

    for key in KindOfMondaiZero.keys():
        if (key&i)==key:
            point+=KindOfMondaiZero[key]
    #print(bin(i),point)

    if point>=g:
        number=min(number,bin(i).count("1"))

print(number)







Fixed submission:
from collections import defaultdict

d, g = map(int, input().split())

scores = []

for i in range(1, d + 1):
    p, c = map(int, input().split())
    scores.append([100 * i, p, c])


result = 10 ** 9
#print(scores)
n = 2 ** d
for i in range(n):
    #print(bin(i))
    cnt = 0
    point = 0
    memo = -1
    for j in range(d):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            point += scores[j][0] * scores[j][1] + scores[j][2]
            cnt += scores[j][1]
        else:
            memo = j

    #print(memo)
    if point >= g:
        result = min(result, cnt)
    else:
        if memo > -1:
            for k in range(scores[memo][1] - 1):
                cnt += 1
                point += scores[memo][0]
                if point >= g:
                    result = min(result, cnt)
                    break

print(result)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())

ab=[]
for _ in range(m):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort((key=lambda x: x[1]))

cnt=0
border=0

for item in ab:
    if item[0]>=border:
        border=item[1]
        cnt+=1

print(cnt)



Fixed submission:
n,m=map(int,input().split())

ab=[]
for _ in range(m):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort()

ll=ab[0][0]
rr=ab[0][1]

cnt=1
#print(ab[0],ll,rr,cnt)
for item in ab[1:]:
    l=item[0]
    r=item[1]
    if l>=rr:
        cnt+=1
        ll=l
        rr=r
    else:
        if r<rr:
            rr=r
        if ll<l:
            ll=l
    #print(item,ll,rr,cnt)

print(cnt)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())

maze=[list(input()) for _ in range(h)]

group=[[0]*w for _ in range(h)]

group_no=0
color_cnt=[]

for y in range(h):
    for x in range(w):
        if group[y][x]==0:
            stack=[(y,x)]
            group_no+=1

            color_cnt_tmp=[0,0]

            while len(stack)>0:
                tmp=stack.pop()
                group[tmp[0]][tmp[1]]=group_no
                print(tmp)
                if maze[tmp[0]][tmp[1]]=="#":
                    color_cnt_tmp[0]+=1
                else:
                    color_cnt_tmp[1]+=1

                for (ny,nx) in [(0,1),(1,0),(-1,0),(0,-1)]:
                    my=ny+tmp[0]
                    mx=nx+tmp[1]
                    if 0<=my<h and 0<=mx<w:
                        if group[my][mx]==0:
                            if maze[tmp[0]][tmp[1]]!=maze[my][mx]:
                                stack.append((my,mx))
                                group[my][mx]=group_no
            color_cnt.append(color_cnt_tmp)

ans=0
for (b,w) in color_cnt:
    ans+=b*w

print(ans)



Fixed submission:
n,m,d=map(int,input().split())

#1~nの数字
#m個
#隣り合う数字がdの個数

if d==0:
    print(1.0*(m-1)/n)
else:
    print(1.0*(m-1)*2*(n-d)/n/n)
Buggy python submission (verdict: Runtime Error):
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
elif
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i//waru)%100 !=0 :
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1


Fixed submission:
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i//waru)%100 !=0 :
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1

Buggy python submission (verdict: Time Limit Exceeded):
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i*100)%waru!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1


Fixed submission:
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i//waru)%100 !=0 :
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1

Buggy python submission (verdict: Runtime Error):
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i*100)%!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1


Fixed submission:
d,n=map(int,input().split())

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i//waru)%100 !=0 :
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())


xyz=[tuple(map(int, input().split())) for _ in range(n)]

#m個食べる
#abs(sum(x))+abs(sum(y))+abs(sum(z))の最大化

#i個中m個食べた時の、最小のxyz
#dp[i][m][0]=(x,y,z)
#i個中m個食べた時の、最大のxyz
#dp[i][m][1]=(x,y,z)

dp=[[[(0,0,0)]*8 for _ in range(m+1)] for _ in range(n)]

for k in range(8):
    dp[0][1][k]=xyz[0]
    dp[0][1][k]=xyz[0]

#- + +
#- - +
#- - - 
#+ + +
#+ - +
#+ - -
#+ + -
#- + -  で最強を目指せば良い

kk=[]
for i in [1,-1]:
    for j in [1,-1]:
        for k in [1,-1]:
            kk.append((i,j,k))

for i in range(1,n):
    for j in range(1,m+1):
        for k in range(8):
            bk=0
            now=0
            for ind in range(3):
                #print(i,j,k,ind,dp)
                #print(kk)
                #print(i,j,k,ind)
                #print(dp[i-1][j][k])
                #print(dp[i-1][j][k][ind])
                #print("kk",kk[k][ind])
                bk+=dp[i-1][j][k][ind]*kk[k][ind]
                now+=dp[i-1][j-1][k][ind]*kk[k][ind]+xyz[i][ind]*kk[k][ind]
            if abs(bk)>abs(now):
                dp[i][j][k]=dp[i-1][j][k]
            else:
                x=dp[i-1][j-1][k][0]*kk[k][ind]+xyz[i][0]*kk[k][0]
                y=dp[i-1][j-1][k][1]*kk[k][ind]+xyz[i][1]*kk[k][1]
                z=dp[i-1][j-1][k][2]*kk[k][ind]+xyz[i][2]*kk[k][2]
                dp[i][j][k]=(x,y,z)

        """
        #最小値
        x=min(dp[i-1][j-1][0][0]+xyz[j][0],dp[i-1][j][0][0])
        y=min(dp[i-1][j-1][0][1]+xyz[j][1],dp[i-1][j][0][1])
        z=min(dp[i-1][j-1][0][2]+xyz[j][2],dp[i-1][j][0][2])
        dp[i][j][0]=(x,y,z)
        #最大値
        x=max(dp[i-1][j-1][1][0]+xyz[j][0],dp[i-1][j][1][0])
        y=max(dp[i-1][j-1][1][1]+xyz[j][1],dp[i-1][j][1][1])
        z=max(dp[i-1][j-1][1][2]+xyz[j][2],dp[i-1][j][1][2])
        dp[i][j][1]=(x,y,z)
        """

ans=0
for item in dp[-1][-1]:
    #print(item)
    ans=max(ans,abs(item[0])+abs(item[1])+abs(item[2]))

print(ans)

Fixed submission:
n,m=map(int,input().split())

xyz=[tuple(map(int, input().split())) for _ in range(n)]
kk=[]
for i in [1,-1]:
    for j in [1,-1]:
        for k in [1,-1]:
            kk.append((i,j,k))

ans=[[] for _ in range(8)]

for (x,y,z) in xyz:
    for i,k in enumerate(kk):
        ans[i].append(x*k[0]+y*k[1]+z*k[2])

result=0

for i in range(8):
    ans[i].sort(reverse=True)
    #print(sum(ans[i][:m]))
    result=max(result,sum(ans[i][:m]))

print(result)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

#初期化
#コイン1円
dp=[i for i in range(n+1)]

#コイン6円
i=1
while 6**i<=n:
    dp[6**i]=1
    i+=1
#コイン6円
i=1
while 9**i<=n:
    dp[9**i]=1
    i+=1

for i in range(1,n+1):
    for j in range(i):
        dp[i]=min(dp[i],dp[j]+dp[i-j])
    #if i%1000==0:
        #print(i)
print(dp[-1])




Fixed submission:
import sys
sys.setrecursionlimit(10**9)


n=int(input())

#dpで解く再帰

memo=[-1]*(n+1)
memo[0]=0

def fuck(x):
    #print(x)
    if memo[x]!=-1:
        return memo[x]
    else:
        tmp=10**9
        #6
        i=1
        while 6**i<=x:
            tmp=min(fuck(x-6**i),tmp)
            i+=1
        #9
        i=1
        while 9**i<=x:
            tmp=min(fuck(x-9**i),tmp)
            i+=1
        #1
        tmp=min(tmp,fuck(x-1))
        memo[x]=tmp+1
        #print(x,tmp+1,memo)
        return tmp+1
fuck(n)
#print(memo)
print(memo[-1])

Buggy python submission (verdict: Runtime Error):
n=int(input())

#初期化
#コイン1円
dp=[i for i in range(n+1)]

#コイン6円
i=1
while 6**i<=n:
    dp[6**i]=1
    i+=1
#コイン6円
i=1
while 9**i<=n:
    dp[9**i]=1
    i+=1

for i in range(1,n+1):
    for j in range(i):
        dp[i]=min(dp[i],dp[j]+dp[i-j])
    if i%1000==0:
        #print(i)
print(dp[-1])




Fixed submission:
import sys
sys.setrecursionlimit(10**9)


n=int(input())

#dpで解く再帰

memo=[-1]*(n+1)
memo[0]=0

def fuck(x):
    #print(x)
    if memo[x]!=-1:
        return memo[x]
    else:
        tmp=10**9
        #6
        i=1
        while 6**i<=x:
            tmp=min(fuck(x-6**i),tmp)
            i+=1
        #9
        i=1
        while 9**i<=x:
            tmp=min(fuck(x-9**i),tmp)
            i+=1
        #1
        tmp=min(tmp,fuck(x-1))
        memo[x]=tmp+1
        #print(x,tmp+1,memo)
        return tmp+1
fuck(n)
#print(memo)
print(memo[-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

ll=0
rr=0
llrr=0

result=0

for ll in range(n):

    while rr<n and a[rr]&llrr==0:
        rr+=1
        b+=a[rr]
    result+=r-list
    b=b^a[ll]

print(result)



    

Fixed submission:
n=int(input())
a=list(map(int,input().split()))

ll=0
rr=0
llrr=0

result=0

for ll in range(n):

    while rr<n and a[rr]&llrr==0:
        llrr+=a[rr]
        rr+=1
    result+=rr-ll
    llrr=llrr^a[ll]

print(result)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

a=[int(input()) for _ in range(n)]
#a(n+1)!=0の時、a(n+1)=a(n)+1である

cnt=0

if a[0]!=0:
    print(-1)
    exit()

b=[0]*n
#print(a)
for ii in range(1,n):
    i=n-ii
    if a[i]==b[i]:
        continue
    elif a[i]<b[i] or a[i]>i:
        print(-1)
        exit()
    else:
        for k in range(a[i]+1):
            b[i-k]=a[i]-k
        cnt+=a[i]

    #print(b)

print(cnt)

    
"""
t: 0 1 1 0 1 2 2 1 2
s: 0 0 0 0 0 0 0 0 0
1: 0 0 1 0 0 0 0 0 0
2: 0 1 1 0 0 0 0 0 0
3: 0 1 1 0 0 0 0 1 0
4: 0 1 1 0 0 0 0 1 2
5: 0 1 1 0 0 1 0 1 2

"""





Fixed submission:
n=int(input())

a=[int(input()) for _ in range(n)]
#a(n+1)!=0の時、a(n+1)=a(n)+1である

cnt=0

if a[0]!=0:
    print(-1)
    exit()
#print(" ".join(list(map(str,a))))
for ii in range(1,n):
    i=n-ii
    if a[i]==0:
        continue
    elif a[i]<=a[i-1]:
        cnt+=a[i]
    elif a[i]==a[i-1]+1:
        cnt+=1
    elif a[i]>a[i-1]+1 or  a[i]>i:
        print(-1)
        exit()
    #print(b)
    #print(" "*(i+1),"^",cnt)

print(cnt)

    
"""
t: 0 1 1 0 1 2 2 1 2
s: 0 0 0 0 0 0 0 0 0
1: 0 0 1 0 0 0 0 0 0
2: 0 1 1 0 0 0 0 0 0
3: 0 1 1 0 0 0 0 1 0
4: 0 1 1 0 0 0 0 1 2
5: 0 1 1 0 0 1 0 1 2

"""
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())

s=[list(input()) for _ in range(h)]

black_cnt=0
for ss in s:
    black_cnt+=ss.count("#")

from collections import deque
stack=deque([(0,0)])
s[0][0]=1

while len(stack)>0:
    #print(stack)
    tmp=stack.popleft()
    if tmp[0]==h-1 and tmp[1]==w-1:
        break

    for (my,mx) in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny=tmp[0]+my
        nx=tmp[1]+mx
        #print(ny,nx)
        if 0<=ny and ny<h and 0<=nx and nx<w:
            #print(ny,nx)
            if s[ny][nx]==".":
                #print(ny,nx,tmp[0],tmp[1],stack)
                s[ny][nx]=s[tmp[0]][tmp[1]]+1
                stack.append((ny,nx))

#for item in s:
 #   print(item)

print(h*w-s[-1][-1]-black_cnt)

    

Fixed submission:
h,w=map(int,input().split())
sx,sy=0,0
gx,gy=w-1,h-1

maze=[]
white=0
for _ in range(h):
    temp=input()
    t=[]
    for s in temp:
        t.append(s)
        if s==".":
            white+=1
    maze.append(t)

maze[sy][sx]=1

from collections import deque
fifo = deque()
fifo.append([sy,sx])

result=-1

while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    if y==gy and x==gx:
        result=maze[y][x]

    if y>0:
        if maze[y-1][x]==".":
            fifo.append([y-1,x])
            maze[y-1][x]=maze[y][x]+1
    if y<h-1:
        if maze[y+1][x]==".":
            fifo.append([y+1,x])
            maze[y+1][x]=maze[y][x]+1
    if x>0:
        if maze[y][x-1]==".":
            fifo.append([y,x-1])
            maze[y][x-1]=maze[y][x]+1
    if x<w-1:
        if maze[y][x+1]==".":
            fifo.append([y,x+1])
            maze[y][x+1]=maze[y][x]+1



if result==-1:
    print(result)
else:
    print(white-result)
Buggy python submission (verdict: Runtime Error):
n=int(input())

a=list(map(int,input().split()))
b=list(map(int,input().split()))

a.sort()
b.sort()

#sum(a)+2*k=sum(b)+k
#k=(sum(a)-sum(b))

k=suma-sumb
#
#1 1 1 6
#2 2 2 3

cnt=0
for i in range(n):
    if a[i]>b[i]:
        cnt+=b[i]-a[i]
    elif a[i]<b[i]:
        cnt+=(-1)*((a[i]-b[i])//2)

if cnt>=k:
    print("Yes")
else:
    print("No")

Fixed submission:
n=int(input())

a=list(map(int,input().split()))
b=list(map(int,input().split()))

#a.sort()
#b.sort()

if a==b:
    print("Yes")
    exit()

suma=sum(a)
sumb=sum(b)


#sum(a)+2*k=sum(b)+k
#k=(sum(a)-sum(b))

k=sumb-suma
#
#1 1 1 6
#2 2 2 3

cnta=0
cntb=0
for i in range(n):
    if a[i]>b[i]:
        cntb+=a[i]-b[i]
    elif a[i]<b[i]:
        cnta+=(-1)*((a[i]-b[i])//2)
#print(k,cntb,cnta)
if cntb<=k and cnta<=k:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
3 5
0 4 3 6 2 7 2 5 3 3
4 0 5 3 7 5 3 7 2 7
5 7 0 7 2 9 3 2 9 1
3 6 2 0 2 4 6 4 2 3
3 5 7 4 0 6 9 7 6 7
9 8 5 2 2 0 4 7 6 5
5 4 6 3 2 3 0 5 4 3
3 6 2 3 4 2 4 0 8 9
4 6 5 4 3 5 3 2 0 8
2 1 3 4 5 7 8 6 4 0
3 5 2 6 1
2 5 3 2 1
6 9 2 5 6

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())

#change[i][j]はiをjに変えるコスト
change=[list(map(int, input().split())) for i in range(10)]
test_case=[list(map(int, input().split())) for i in range(h)]
cost=[0]*10

for i in range(10):
    cost[i]=change[i][1]
#print(cost)
def DEF(start,backed,weight,non_used):
    global cost,change
    #print(backed,non_used)
    if non_used==[]:
        return 0

    for item in non_used:
        if weight+change[backed][item]+change[item][1]<cost[start]:
            cost[start]=weight+change[backed][item]+change[item][1]
        if weight+change[backed][item]<cost[start]:
            non_used2=[]
            for t in non_used:
                if t!=item:
                    non_used2.append(t)

            DEF(start,item,weight+change[backed][item],non_used2)

for item in range(10):
    if item!=1:

        temp=[]
        for i in range(10):
            if item!=i and i!=1:
                temp.append(i)
        #print("######",item,temp)
        DEF(item,item,0,temp)

result=0
for item in test_case:
    for item2 in item:
        if item2!=1 and item2!=-1:
            result+=cost[item2]

print(result)
Buggy python submission (verdict: Runtime Error):
n,z,w=map(int,input().split())
card=list(map(int,input.split()))

if n==1:
  print(abs(card[0]-w))
else:
  print(max(abs(n[-2]-n[-1]),abs(n[-1]-w)))

Fixed submission:
n,z,w=map(int,input().split())
card=list(map(int,input().split()))

if n==1:
  print(abs(card[0]-w))
else:
  print(max(abs(card[-2]-card[-1]),abs(card[-1]-w)))
Buggy python submission (verdict: Runtime Error):
#https://atcoder.jp/contests/abc076/tasks/abc076_c

s=input()
t=input()

for i in range(len(s)-len(t)+1):
    flag=0
    n= len(s)-i-len(t)
    temp=s[n:n+len(t)]
    for j in range(len(t)):
        if temp[j]!=t[j] and temp[j]!="?":
            flag=1
    if flag==0:
        break

if flag==1:
    print("UNRESTORABLE")
    exit()
temp=s[:n]+t+s[n+len(t):]
print(temp.replace("?","a"))


Fixed submission:
s=list(input())
t=input()

for i in range(len(s)-len(t)+1):
    flag=0
    i=len(s)-len(t)-i
    #print(i)
    for j in range(len(t)):
        if t[j]!=s[i+j] and s[i+j]!="?":
            flag=1
            #print(j,t[j],s[i+j])
    if flag==0:
        for j in range(len(t)):
            s[i+j]=t[j]
        result=""
        for item in s:
            result=result+str(item)
        result=result.replace("?","a")
        print(result)
        exit()
print("UNRESTORABLE")
Buggy python submission (verdict: Time Limit Exceeded):
n,m,r=map(int,input().split())
r=list(map(int,input().split()))

import sys
INF=float('inf')

road=[[INF]*n for _ in range(n)]

for _ in range(m):
    a,b,c=map(int,input().split())
    road[a-1][b-1]=c
    road[b-1][a-1]=c

#経由地
for k in range(n):
    #出発地
    for s in range(n):
        #goal
        for g in range(n):
            road[s][g]=min(road[s][g],road[s][k]+road[k][g])

import itertools
rlist=list(itertools.permutations(r))

result=10**9
for item in rlist:
    tmp=0
    from_town=item[0]
    for to_town in item[1:]:
        tmp+=road[from_town-1][to_town-1]
        from_town=to_town
    result=min(result,tmp)

print(result)





Fixed submission:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))

import sys
INF=float('inf')

road=[[INF]*n for _ in range(n)]

for _ in range(m):
    a,b,c=map(int,input().split())
    road[a-1][b-1]=c
    road[b-1][a-1]=c

#経由地
for k in range(n):
    #出発地
    for s in range(n):
        #goal
        for g in range(n):
            road[s][g]=min(road[s][g],road[s][k]+road[k][g])

import itertools
rlist=list(itertools.permutations(r))

result=10**9
for item in rlist:
    tmp=0
    from_town=item[0]
    for to_town in item[1:]:
        tmp+=road[from_town-1][to_town-1]
        from_town=to_town
    result=min(result,tmp)

print(result)
Buggy python submission (verdict: Runtime Error):
a=list(input())

unko=[0]*(ord("z")+1-ord("a"))

for aa in a:
    unko[ord(aa)-ord("a")]+=1
tmp=0
for u in unko:
    tmp+=(u*(u-1))//2

print((n*(n-1))//2-tmp)

Fixed submission:
a=list(input())

unko=[0]*(ord("z")+1-ord("a"))

for aa in a:
    unko[ord(aa)-ord("a")]+=1
tmp=0
for u in unko:
    tmp+=(u*(u-1))//2

print((len(a)*(len(a)-1))//2-tmp+1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s1=input()
s2=input()

mod=1000000007

x=0
cnt=1
while x<3:
    if x==0:
        if s1[x]==s2[x]:
            cnt*=3%mod
            x+=1
        else:
            cnt*=6%mod
            x+=2
    else:
        if s1[x-1]==s2[x-1]:
            #x-1:AA 
            #x  :BB CC
            if s1[x]==s2[x]:
                cnt*=2%mod
                x+=1
            #x-1:AA 
            #x  :BC  CB
            #    BC  CB
            else:
                cnt*=2%mod
                x+=2
        else:
            #x-1:AB
            #   :CC
            if s1[x]==s2[x]:
                cnt*=1%mod
                x+=1
            #x-1:AB
            #x  :BA CA BC 
            else:
                cnt*=3%mod
                x+=2

print(cnt%mod)






Fixed submission:
n=int(input())
s1=input()
s2=input()

mod=1000000007

x=0
cnt=1
while x<n:
    if x==0:
        if s1[x]==s2[x]:
            cnt*=3%mod
            x+=1
        else:
            cnt*=6%mod
            x+=2
    else:
        if s1[x-1]==s2[x-1]:
            #x-1:AA 
            #x  :BB CC
            if s1[x]==s2[x]:
                cnt*=2%mod
                x+=1
            #x-1:AA 
            #x  :BC  CB
            #    BC  CB
            else:
                cnt*=2%mod
                x+=2
        else:
            #x-1:AB
            #   :CC
            if s1[x]==s2[x]:
                cnt*=1%mod
                x+=1
            #x-1:AB
            #x  :BA CA BC 
            else:
                cnt*=3%mod
                x+=2

print(cnt%mod)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))

a.sort()
#9,4,3>7
#9-(9-4-3)


#9 ;6 3 >5
if k in a:
    print("POSSIBLE")
    exit()

if k>a[-1]:
    print("IMPOSSIBLE")
    exit()

if a[0]==1:
    print("POSSIBLE")
    exit()

flag=0
for item in a[1:]:
    if item%a[0]!=0:
        flag=1

if flag==1:
    print("POSSIBLE")
    exit()
else:
    if k%item[0]==0:
        print("POSSIBLE")
        exit()
    else:
        print("IMPOSSIBLE")
        exit()




Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import fractions
a.sort()
#9,4,3>7
#9-(9-4-3)
#9 ;6 3 >5
if k in a:
    print("POSSIBLE")
    exit()

if k>a[-1]:
    print("IMPOSSIBLE")
    exit()

if a[0]==1:
    print("POSSIBLE")
    exit()

flag=0
gg = fractions.gcd(a[0], a[1])

for item in a[1:]:
    if item%gg!=0:
        flag=1

if flag==1:
    print("POSSIBLE")
    exit()
else:
    if k%gg==0:
        print("POSSIBLE")
        exit()
    else:
        print("IMPOSSIBLE")
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b=map(int,input().split())
h=[-1*int(input()) for _ in range(n)]

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

heapq.heapify(h)

#直撃a、爆風b
cnt=1
while 1:
    tmp=heapq.heappop(h)*(-1)
    tmp=tmp-a+b
    heapq.heappush(h,(-1)*tmp)
    
    if h[0]*(-1)-b*cnt<=0:
        print(cnt)
        break
    cnt+=1






Fixed submission:
n,a,b=map(int,input().split())
h=[int(input()) for _ in range(n)]

#二部探索

ll=0
rr=10**9+1
ab=a-b
while ll<rr:
    half=(ll+rr)//2

    cnt=0
    for hh in h:
        if hh>b*half:
            cnt+=(-1*((-1*(hh-b*half))//ab))
    
    if cnt>half:
        ll=half+1
    elif cnt<half:
        rr=half
    else:
        print(half)
        exit()
print(ll)

Buggy python submission (verdict: Time Limit Exceeded):
n,a,b=map(int,input().split())
h=[-1*int(input()) for _ in range(n)]

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

heapq.heapify(h)

#直撃a、爆風b
cnt=1
while 1:
    tmp=heapq.heappop(h)*(-1)
    tmp=tmp-a+b
    heapq.heappush(h,(-1)*tmp)

    tmp=heapq.heappop(h)*(-1)
    
    if tmp-b*cnt<=0:
        print(cnt)
        break
    heapq.heappush(h,tmp*(-1))
    cnt+=1






Fixed submission:
n,a,b=map(int,input().split())
h=[int(input()) for _ in range(n)]

#二部探索

ll=0
rr=10**9+1
ab=a-b
while ll<rr:
    half=(ll+rr)//2

    cnt=0
    for hh in h:
        if hh>b*half:
            cnt+=(-1*((-1*(hh-b*half))//ab))
    
    if cnt>half:
        ll=half+1
    elif cnt<half:
        rr=half
    else:
        print(half)
        exit()
print(ll)