Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=int(input())  #数値入力 「N」だけの入力のとき

S = []
for _ in range(n):
    S.append(set(input()).sort())
print(n-len(set(S)))

Fixed submission:
import collections
N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
C=collections.Counter(S)
ans=0
for si in set(S):
  n=C[si]
  ans+=n*(n-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())  #数値入力 「N」だけの入力のとき

S = []
for _ in range(n):
    S.append(set(input()).sort())
print(n-len(set(S))+1)

Fixed submission:
import collections
N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
C=collections.Counter(S)
ans=0
for si in set(S):
  n=C[si]
  ans+=n*(n-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())  #数値入力 「N」だけの入力のとき

S = []
for _ in range(n):
    S.append(set(input()).sort)
print(n-len(set(S))+1)

Fixed submission:
import collections
N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
C=collections.Counter(S)
ans=0
for si in set(S):
  n=C[si]
  ans+=n*(n-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())  #数値入力 「N」だけの入力のとき

S = []
for _ in range(H):
    S.append(set(input()).sort)
print(n-len(set(S))+1)

Fixed submission:
import collections
N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
C=collections.Counter(S)
ans=0
for si in set(S):
  n=C[si]
  ans+=n*(n-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())

if n<10:
  print(n)
elif n<100:
  print(9)
elif n<1000:
  print(n-90)
elif n<10000:
  print(909)
else n<100000:
  print(n-9090)
else:
  print(90909)

Fixed submission:
n=int(input())

if n<10:
  print(n)
elif n<100:
  print(9)
elif n<1000:
  print(n-90)
elif n<10000:
  print(909)
elif n<100000:
  print(n-9090)
else:
  print(90909)
Buggy python submission (verdict: Runtime Error):
N=int(input())
H=list(map(int,input().split()))
pre=-999
for i in range(N):
  if pre<=H[i]-1:
    pre=H[i]-1
  else if pre<=H[i]:
    pre=H[i]
  else:
    print('No')
else:print('Yes')

Fixed submission:
N=int(input())
H=list(map(int,input().split()))
pre=-999
for i in range(N):
  if pre<=H[i]-1:
    pre=H[i]-1
  elif pre<=H[i]:
    pre=H[i]
  else:
    print('No')
    break
else:
  print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): #整数のときはその値について更新する
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

Fixed submission:
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): #整数のときはその値について更新する
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=sorted(list(map(int,input().split())))
M=A[0]
for i in range(N):
  if i==M:
    print(A[1])
  else:
    print(M)
 
    

Fixed submission:
N=int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A2=sorted(A,reverse=True)
M=A2[0]
M2=A2[1]
for i in range(N):
  #print(A[i])
  
  if A[i]==M:
    print(M2)
  else:
    print(M)
Buggy python submission (verdict: Runtime Error):
N=int(input())
D=list(map(int,input().split()))
DS=sorted(D)
ans=DS[N//2]-DS[D//2-1]
print(ans)

Fixed submission:
N=int(input())
D=list(map(int,input().split()))
D=sorted(D)
ans=D[N//2]-D[N//2-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
A = [int(input()) for _ in range(m)]
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])


Fixed submission:
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[]
for i in range(M):
  A.append(int(input()))
ans=0
MOD=1000000007
dp=[]
for i in range(N-1,0,-1):
  if i in A:
    dp[i]=0
    continue
  dp[i]=dp[i+1]+dp[i+2]
  
ans=dp[0]
ans/=MOD
print(ans)
           


Fixed submission:
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])
Buggy python submission (verdict: Runtime Error):
N=int(input())
SP=[]
for i in range(N):
  S,P=input()
  SP.append([S,int(P),i+1])
  
l=sorted(SP,key = lamda SP : (SP[0],-SP[1]))

for i in l:
  print(SP[2])

Fixed submission:
N=int(input())
SP=[]
for i in range(N):
  S,P=input().split()
  SP.append([S,int(P),i+1])
  
l=sorted(SP,key = lambda SP : (SP[0],-SP[1]))

for i in l:
  print(i[2])
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
res=0
for i in range(N):
  tmp=1
  cnt=i
  while cnt<K:
    cnt*=2
    tmp/=2
  res+=tmp
res/=N
print(res)

Fixed submission:
N,K=map(int,input().split())
ans=0
for i in range(1,N+1):
  cnt=i
  pro=1
  while cnt<K:
    cnt*=2
    pro/=2
  pro/=N
  #print(pro)
  ans+=pro
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
res=0
for i in range(N):
  tmp=1
  cnt=i
  while cnt<K:
    cnt*=2
    tmp/=2
  res+=tmp
res/=N
print(res)
  


Fixed submission:
N,K=map(int,input().split())
ans=0
for i in range(1,N+1):
  cnt=i
  pro=1
  while cnt<K:
    cnt*=2
    pro/=2
  pro/=N
  #print(pro)
  ans+=pro
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
K=int(input())
for i in range(N):
  if S[K-1]==S[i]:
    S[i]='*'
print(S)

Fixed submission:
input()
S=input()
k=int(input())
for s in S:print(s if s==S[k-1] else "*",end="")

Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
K=int(input())
for i in S:
  if S[K-1]==S[i]:
    S[i]='*'
print(S)

Fixed submission:
input()
S=input()
k=int(input())
for s in S:print(s if s==S[k-1] else "*",end="")

Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
K=int(input())
for i in S:
  if S[K]==S[i]:
    S[i]='*'
print(S)

Fixed submission:
input()
S=input()
k=int(input())
for s in S:print(s if s==S[k-1] else "*",end="")
Buggy python submission (verdict: Runtime Error):
N = int(input())
ls = [int(input()) for range(5)]
X = min(ls)
print((N+X-1)//X+4)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(5)]
X=min(A)
ans=(N+X-1)//X +4
print(ans)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[int(input()) for range(N)]
X=min(A)
ans=(N+X-1)//X +4
print(ans)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(5)]
X=min(A)
ans=(N+X-1)//X +4
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = list(input())
p = [tuple(map(str,input().split())) for i in range(q)]

#s[x]が左へ抜けるか O(q)
def judge_left(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return True
        if x == n:
            return False
    return False

#s[x]が右へ抜けるか O(q)
def judge_right(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return False
        if x == n:
            return True
    return False

#どこまで左で抜けるか
ok = -1
ng = n
while ng-ok > 1:
    mid = (ng+ok)//2
    if judge_left(mid):
        ok = mid
    else:
        ng = mid
left = ok+1

#どこまで右で抜けるか
ok = n
ng = -1
while ok-ng >1:
    mid = (ok+ng)//2
    if judge_right(mid):
        ok = mid
    else:
        ng = mid
right = n-ok

print(max(n-left-right,0))

Fixed submission:
n,q = map(int,input().split())
s = list(input())
p = [tuple(map(str,input().split())) for i in range(q)]

#s[x]が左へ抜けるか O(q)
def judge_left(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return True
        if x == n:
            return False
    return False

#s[x]が右へ抜けるか O(q)
def judge_right(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return False
        if x == n:
            return True
    return False

#どこまで左で抜けるか
ok = -1
ng = n
while ng-ok > 1:
    mid = (ng+ok)//2
    if judge_left(mid):
        ok = mid
    else:
        ng = mid
left = ok+1

#どこまで右で抜けるか
ok = n
ng = -1
while ok-ng >1:
    mid = (ok+ng)//2
    if judge_right(mid):
        ok = mid
    else:
        ng = mid
right = n-ok

print(max(n-left-right,0))
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
h,w=map(int,input().split())
ptint((H-h)*(W-w))

Fixed submission:
H,W=map(int,input().split())
h,w=map(int,input().split())
print((H-h)*(W-w))

Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
h,w=map(int,input().split())
ptint((H-h)*((W-w))

Fixed submission:
H,W=map(int,input().split())
h,w=map(int,input().split())
print((H-h)*(W-w))
Buggy python submission (verdict: Runtime Error):
A,B,C=map(int(),input().split())
print((A*B)//2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
A,B,C=map(int(),input().split())
print(A*B//2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
A,B,C=map(int(),input().split())
print(A*B/2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
print(a*b//2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,(input().split())
print(a*b//2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
a,b,c=map(int(input().split())
print(a*b//2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
a,b,c=map(int(input().split())
print(a*b/2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)

Buggy python submission (verdict: Runtime Error):
a,b=int(input())
print(a*b/2)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)
Buggy python submission (verdict: Time Limit Exceeded):
dp=[0]*110000
LINF=10**9

n,k=map(int,input().split())
h=list(map(int,input().split()))

dp[0]=0
for i in range(1,n):
  dp[i]=LINF
  for j in range(1,k+1):
    if i-j>=0:
      dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
H=list(map(int,input().split()))
INF=1000000000
dp=[INF]*(N+1)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if (i-j)>=0:
      dp[i]=min(dp[i],dp[i-j]+abs(H[i-j]-H[i]))
print(dp[N-1])

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Buggy python submission (verdict: Runtime Error):
N = int(input())
H=list(map(int,input().split()))
INF=1000000000
dp=[INF]*(N+1)
dp[0]=0
for i in range(1,N):
  if i==1:
    dp[i]=dp[i-1]+abs(H[i]-H[i-1])
  else:
    dp[i]=min(dp[i-2]+abs(H[i-2]-H[i]),dp[i-1]+abs(H[i-1]-H[i]))
print(dp[N-1])

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
H=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+5)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if (i-j)<0:
      continue
    dp[i]=min(dp[i-j]+abs(H[i-j]-H[i]),dp[i])
print(dp[N-1])

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])

Fixed submission:
N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
INF=10**10
for j in range(1,110000):
  dp[0][j]=INF

for i in range(1,n+1):
  for j in range(110000):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][1]>=0:
      dp[i][j]=min(dp[i][j],
                   dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
ans=0
for v in range(110000):
  if dp[n][v]<=W:
    ans=max(ans,v)
      
print(ans)

Fixed submission:
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
INF=10**10
for j in range(1,110000):
  dp[0][j]=INF

for i in range(1,n+1):
  for j in range(110000):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][1]>=0:
      dp[i][j]=min(dp[i][j],
                   dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
ans=0
for v in range(110000):
  if dp[n][v]<=W:
    ans=max(ans,v)
      
print(ans)
Buggy python submission (verdict: Runtime Error):
X=int(input())
if (X==3 || X==5 ||X==7):
  print('YES')
else:
  print('NO')

Fixed submission:
x=input()
if x in "753":
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Runtime Error):
'''Yoshichiの日記
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。
現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、
                   次の隣へも線が引かれている状態)
'''
h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))
def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Fixed submission:
'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)）
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に
if W != 1: #棒が一本以上あるときは
  for i in range(1,H+1):
    for j in range(W): #棒が左端、右端、それ以外で場合分け
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7)) #高さH（一番下）、K-1番目の棒を調べる
Buggy python submission (verdict: Runtime Error):
A=input()
for i in range(3):
  if A[i]=='1':
    A[i]='9'
  else if A[i]=='9':
    A[i]='1'
print('A')

Fixed submission:
n = input()
for c in n:
    if (c == '1'):
        print('9', end='')
    elif (c == '9'):
        print('1', end='')
    else:
        print(c, end='')
print()

Buggy python submission (verdict: Runtime Error):
A=input()
for i in range(3):
  if A[i]=='1':
    A[i]='9'
  else if A[i]=='9':
    A[i]='1'
print(A)

Fixed submission:
n = input()
for c in n:
    if (c == '1'):
        print('9', end='')
    elif (c == '9'):
        print('1', end='')
    else:
        print(c, end='')
print()

Buggy python submission (verdict: Runtime Error):
A=int(input().split())
for i in range(3):
  if A[i]==1:
    A[i]=9
  else if A[i]==9:
    A[i]=1
print(A)

Fixed submission:
n = input()
for c in n:
    if (c == '1'):
        print('9', end='')
    elif (c == '9'):
        print('1', end='')
    else:
        print(c, end='')
print()
Buggy python submission (verdict: Runtime Error):
A,B,C=(map(int,input().split())).sort()
print(10*C+B+A)

Fixed submission:
A,B,C=sorted(map(int,input().split()))
print(10*C+A+B)
Buggy python submission (verdict: Runtime Error):
S=input()
K=int(input())
cnt=0
i=0
while S[i]=='1':
  cnt+=1
  i+=1
if cnt>K:
  ans=1
else:
  ans=S[cnt]
print(ans)

Fixed submission:
s = str(input())
k = int(input())

for i in range(min(len(s),k)):
#「Sの長さ」と「K」の少ない方の回数分ループを回す
    if s[i] != '1':#Kまで１が続かなかったら
        print(s[i])#最初に出てきた１以外の数が出力される
        exit()#ループを抜けて終了

print('1')#Kまで１が続けば、１が出力される
Buggy python submission (verdict: Runtime Error):
N=int(input())
if N%2==0:
  ans=N
else:
  ans=2N
print(ans)

Fixed submission:
N=int(input())
if N%2==0:
  ans=N
else:
  ans=2*N
print(ans)
Buggy python submission (verdict: Runtime Error):
A,B=map(int,input().split())
X=A*B
Y=A-B
X=A+B
print(max(X,Y,Z))

Fixed submission:
A,B=map(int,input().split())
X=A*B
Y=A-B
Z=A+B
print(max(X,Y,Z))
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if abs(a-c)<=d:
  print('Yes')
else if abs(b-c)<=d and abs(a-b)<=d:
  print('Yes')
else:
  print('No')

Fixed submission:
a,b,c,d=map(int,input().split())
if abs(a-c)<=d:
  print('Yes')
elif abs(b-c)<=d and abs(a-b)<=d:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
L=[cha[i] for i in int().split()]
sorted.L
if L=='abc':
  print('Yes')
else :
  print('No')

Fixed submission:
L=set(input())
if len(L)==3:
  print('Yes')
else :
  print('No')
Buggy python submission (verdict: Runtime Error):
N=int(input())
N+=2
ans=N//3
ans-=
print(ans)


Fixed submission:
n=int(input())
print(n//3)
Buggy python submission (verdict: Runtime Error):
N=int(input())
Flag=False
for i in range(N):
  C=input()
  if C=='Y':
    Flag=True
    
print('Four' if Flag else 'Three')
  

Fixed submission:
input()
print("Four" if "Y" in input() else "Three")
Buggy python submission (verdict: Runtime Error):
def MI(): return map(int, input().split())
from collections import deque
H,W=MI()
#Map=[[]*W for _ in range(H)]
Map=[]
white=0
for _ in range(H):
  Map.append(list(input()))
def bfs():
  dx=[-1,0,1,0]
  dy=[0,-1,0,1]
  INF=float('inf')
  dist=[[INF]*W for _ in range(H)]
  dist[0][0]=0
  que=deque()
  que.append((0,(0,0)))

  while que:
    d,(x,y) =que.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if 0<=nx<H and 0<=ny<W:
        if Map[nx][ny]!='#':
          if dist[nx][ny]==INF:
            dist[nx][ny]=d+1
            que.append((d+1,(nx,ny)))
  return dist
res=bfs()  
for i in range(H):
  for j in range(W):
    if Map[i][j]=='.':
      white+=1
ans=white-res[H-1][W-1]-1
if 0<ans<INF:
  print(ans)
else:
  print(-1)

Fixed submission:
from collections import deque


def bfs():
    d = [[float("inf")] * w for i in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
sx, sy = 0, 0
gx, gy = h - 1, w - 1

# 白いマスを数える
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            white += 1

res = bfs()
if 0 < res < float("inf"):
    # 白いマスの数から最短経路でかかるコスト分を引く
    # ゴールを黒いマスに変えることはできないためその分も引く
    print(white - res - 1)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a*b%2=0:
  print('Even')
else:
  print('Odd')

Fixed submission:
a,b=map(int,input().split())
if a*b%2:
  print('Odd')
else:
  print('Even')
Buggy python submission (verdict: Runtime Error):
S=input()
S[3]='7'
print(S)

Fixed submission:
S = input()
print(S.replace("2017/", "2018/", 1))
Buggy python submission (verdict: Runtime Error):
l=[map(int,input().split(''))]
c=0
for i in l:
  if i=='1':
    c+=1
print(c)  


Fixed submission:
l=input()
c=0
for i in l:
  if i=='1':
    c+=1
print(c)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))

ans=10**9

for i in A:
  p=0
  while i%2 ==0:
    i=/2
    p+=1
  if p<ans:
    ans=p
    
print(ans)

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

ans=10**9

for i in A:
  p=0
  while i%2 ==0:
    i/=2
    p+=1
  if p<ans:
    ans=p
    
print(ans)

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

ans=10**9

for i in A:
  p=0
  while i % 2 ==0:
    i=/2
    p+=1
  if p<ans:
    ans=p
    
print(ans)

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

ans=10**9

for i in A:
  p=0
  while i%2 ==0:
    i/=2
    p+=1
  if p<ans:
    ans=p
    
print(ans)