TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
H,W,K = map(int, input().split())

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        for l in range(W-1):
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
          else:
            dp[i+1][l] += dp[i][l]
        #print(dp[i+1])

  print(dp[-1][K-1]%(1000000007)

H,W,K = map(int, input().split())

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print('Ans=',1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        #print('pre',dp[i])
        #print(dp[i+1])

  print('Ans=',dp[-1][K-1]%(1000000007))

        
        
          

H,W,K = map(int, input().split())

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        #print('pre',dp[i])
        #print(dp[i+1])

  print(dp[-1][K-1]%(1000000007))

        
        
          

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
h, w, k = map(int, input().split())
a = [0]*(w-1) + [1,1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
    dp, tmp = tmp, dp
print(dp[k-1])

h, w, k = map(int, input().split())
a = [0]*(w-1) + [1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
        tmp[i] %= m
    dp, tmp = tmp, dp
print(dp[k-1])

h, w, k = map(int, input().split())
a = [0]*(w-1) + [0,1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
    dp, tmp = tmp, dp
print(dp[k-1])

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
def main():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(1 << (W - 1)):
            if '11' in bin(j):
                continue
            j <<= 1
            for w in range(W):
                if j & (1 << w):
                    dp[i + 1][w] += dp[i][w - 1]
                elif j & (1 << (w + 1)):
                    dp[i + 1][w] += dp[i][w + 1]
                else:
                    dp[i + 1][w] += dp[i][w]
                dp[i + 1][w] %= (10 ** 9 + 7)

    for a in dp:
        print(a)
    print(dp[H][K - 1])


if __name__ == '__main__':
    main()


def main():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(1 << (W - 1)):
            if '11' in bin(j):
                continue
            j <<= 1
            for w in range(W):
                if j & (1 << w):
                    dp[i + 1][w] += dp[i][w - 1]
                elif j & (1 << (w + 1)):
                    dp[i + 1][w] += dp[i][w + 1]
                else:
                    dp[i + 1][w] += dp[i][w]
                dp[i + 1][w] %= (10 ** 9 + 7)

    print(dp[H][K - 1])


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
h,w,k = list(map(int,input().split()))

mat = [[0 for i in range(w+1)] for j in range(h+1)]
mat[0][0]=1

for i in range(1,h+1):
    for j in range(w):
        if j==0:
            mat[i][j]=mat[i-1][j]+mat[i-1][j+1]
        elif j==w-1:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]
        else:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]+mat[i-1][j+1]

print(mat[h-1][k-1] % 1000000007)


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

mat = [[0 for i in range(w)] for j in range(h)]
mat[0][0]=1

for i in range(1,h):
    for j in range(w):
        if j==0:
            mat[i][j]=mat[i-1][j]+mat[i-1][j+1]
        elif j==w-1:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]
        else:
            mat[i][j]=mat[i-1][j]+mat[i-1][j-1]+mat[i-1][j+1]

print(mat[h-1][k-1] % 1000000007)


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

mat = [[0 for _ in range(w)] for __ in range(h+1)]
mat[0][0] = 1


def num(n):
    ret = 0
    if n == 0:
        return 1
    for i in range(2**(n-1)):
        dig = format(i, 'b')
        if not '11' in dig:
            ret += 1

    return ret


if w == 1:
    print('1')
    exit()

for col in range(1, h+1):
    for row in range(w):
        if row == 0:
            mat[col][row] = mat[col-1][row] * \
                num(w-1) + mat[col-1][row+1]*num(w-2)
        elif row == w-1:
            mat[col][row] = mat[col-1][row] * \
                num(w-1) + mat[col-1][row-1]*num(w-2)
        else:
            mat[col][row] = mat[col-1][row] * (num(row)*num(w-row-1)) \
                + mat[col-1][row-1]*(num(row-1)*num(w-row-1))\
                + mat[col-1][row+1]*(num(row)*num(w-row-2))
print(mat[h][k-1] % 1000000007)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
h, w, k = map(int, input().split())
mod = 10 ** 9 + 7

dp = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(w + 1):
  dp[0][i] = 1 if i == 1 else 0


def calc_pow(from_col, to_col):
  assert(1<=from_col<=w and 1<=to_col<=w)
  if from_col == 1 or to_col == 1 or from_col == w or to_col == w:
    return pow(2, max(w-1-2, 0), mod)
  else:
    return pow(2, max(w-1-3, 0), mod)


for t in range(1, h + 1):
  for i in range(1, w + 1):
    pattern_1 = dp[t-1][i-1] * calc_pow(i-1, i) if i > 1 else 0
    pattern_2 = dp[t-1][i+1] * calc_pow(i+1, i) if i < w else 0
    pattern_3 = dp[t-1][i] * (pow(2, max(w-1-2, 0), mod) if 1 < i < w else pow(2, max(w-1-1, 0), mod))
    dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

for line in dp:
  print(*line)
# print(dp[h][k])


from itertools import product

h, w, k = map(int, input().split())
mod = 10 ** 9 + 7

dp = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(w + 1):
    dp[0][i] = 1 if i == 1 else 0


def check_valid_bridge(bridge):
    for i in range(1, w-1):
        if bridge[i-1] and bridge[i]:
            return False
    return True

for t in range(1, h + 1):
    for i in range(1, w + 1):
        X, Y, Z = 0, 0, 0
        if w != 1:
            p = product([True, False], repeat=w-1)            
            for bridge in p:
                if check_valid_bridge(bridge):
                    if i > 1 and bridge[i-2]:
                        X += 1
                    elif i < w and bridge[i-1]:
                        Y += 1
                    elif (i == 1 and not bridge[i-1]) or (i == w and not bridge[i-2]) or (1 < i < w and not bridge[i-2] and not bridge[i-1]):
                        Z += 1
        else:
            Z = 1
        # print(f"{X} {Y} {Z}")
        pattern_1 = dp[t-1][i-1] * X if i > 1 else 0
        pattern_2 = dp[t-1][i+1] * Y if i < w else 0
        pattern_3 = dp[t-1][i] * Z
        dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

# for line in dp:
#     print(*line)
print(dp[h][k])


Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):

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))


from collections import defaultdict
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))

Verdicts: Runtime Error

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
MOD = 10 ** 9 +7
h, w, k = map(int,input().split())

if w == 1:
    print(1)
else:
    acr = []
    for p in range(2**(w-1)):
        det = 0
        pp = p
        exist = [0] * (w-1)
        for i in range(w-1):
            exist[i] = pp % 2
            pp = pp // 2
        for ii in range(w-2):
            if exist[ii] == 1 and exist[ii+1] == 1:
                det = 1
        if det == 0:
            acr.append(exist)

    cur = [0] * w
    cur[0] = 1
    n = [0] * w

    for x in range(len(acr)):
        n[0] = cur[1] * acr[x][0] + cur[0] * (1-acr[x][0])
        for j in range(1,w-1):
            n[j] = cur[j-1] * acr[x][j-1] + cur[j+1] * acr[x][j] + cur[j] * (1-acr[x][j-1])(1-acr[x][j])
        n[w-1] = cur[w-2] * acr[x][w-2] + cur[w-1] * (1-acr[x][w-1])
        cur = n[:]
    print(cur[k-1])

MOD = 10 ** 9 +7
h, w, k = map(int,input().split())

if w == 1:
    print(1)
else:
    acr = []
    for p in range(2**(w-1)):
        det = 0
        pp = p
        exist = [0] * (w-1)
        for i in range(w-1):
            exist[i] = pp % 2
            pp = pp // 2
        for ii in range(w-2):
            if exist[ii] == 1 and exist[ii+1] == 1:
                det = 1
        if det == 0:
            acr.append(exist[:])
    #print(acr)

    cur = [0] * w
    cur[0] = 1
    

    for t in range(h):
        n = [0] * w
        for x in range(len(acr)):
            n[0] = (n[0] + cur[1] * acr[x][0] + cur[0] * (1-acr[x][0]))%MOD
            for j in range(1,w-1):
                n[j] = (n[j] + cur[j-1] * acr[x][j-1] + cur[j+1] * acr[x][j] + cur[j] * (1-acr[x][j-1])*(1-acr[x][j]))%MOD
            n[w-1] = (n[w-1] + cur[w-2] * acr[x][w-2] + cur[w-1] * (1-acr[x][w-2])) % MOD
        
        cur = n[:]
        
    print(cur[k-1])

Verdicts: Runtime Error

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
import itertools

H,W,K = map(int, input().split())
p = 1000000007

if K - 1 > H:
    print(0)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

print(R)
print(M)

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)    
    


import itertools

H,W,K = map(int, input().split())
p = 1000000007

if K - 1 > H:
    print(0)
    exit(0)
if W == 1:
    print(1)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)    
    


Verdicts: Runtime Error

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

H, W, K = map(int, input().split())

dp = [0] * W
dp[0] = 1

for _ in range(H):

    T = [0] * W

    for i in range(W):
        if 0 < i:
            T[i] += T[i - 1] * fib[i - 1] * fib[W - i - 1]

        T[i] += T[i] * fib[i] * fib[W - i - 1]

        if i < W - 1:
            T[i] += dp[i + 1] * fib[i] * fib[W - i - 2]

        T[i] %= mod

    dp = T

print(dp[K - 1])

mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

H, W, K = map(int, input().split())

dp = [0] * W
dp[0] = 1

for _ in range(H):

    T = [0] * W

    for i in range(W):
        if 0 < i:
            T[i] += dp[i - 1] * fib[i - 1] * fib[W - i - 1]

        T[i] += dp[i] * fib[i] * fib[W - i - 1]

        if i < W - 1:
            T[i] += dp[i + 1] * fib[i] * fib[W - i - 2]

        T[i] %= mod

    dp = T

print(dp[K - 1])

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
H, W, K = map(int, input().split())
mod = 7 + 10**9
No = [1 for i in range(7)] 
No[1], No[2], No[3], No[4] = 2, 3, 5, 8
No[5], No[6]= 13, 21

if W == 1:
    print(1)
else:
    DP = [[0 for w in range(W)] for h in range(H)]
    DP[0][0], DP[0][1] = No[max(0, W-2)], No[max(0, W-3)]
    for h in range(1, H):
        for w in range(W):
            if w == 0:
                left = 0
                up = DP[h-1][0] * No[max(0, W-2)] % mod
                right = DP[h-1][1] * No[max(0, W-3)] % mod
            elif w == W-1:
                left = DP[h-1][W-2] * No[max(0, W-3)] % mod
                up = DP[h-1][W-1] * No[max(0,W-2)] % mod
                right = 0
            else:
                left = DP[h-1][w-1] * No[max(0, w-2)] * No[max(0, W-w-2)] % mod
                up = DP[h-1][w] * No[max(0, w-1)] * No[max(0, W-w-2)] % mod
                right = DP[h-1][w+1] * No[max(0, w-1)] * No[max(0, W-w-3)] % mod
            DP[h][w] = (left+up+right) % mod
    print(DP)
    print(DP[H-1][K-1])

import sys
mod = 7 + 10 ** 9

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    DP = [[0] * W for _ in range(H + 1)]
    pattern = [1, 2, 3, 5, 8, 13, 21]
    DP[0][0] = 1
    for h in range(H):
        for w in range(W):
            if w == 0:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w+1] * pattern[max(0, W - 3)]) % mod
            elif w == W - 1:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w-1] * pattern[max(0, W - 3)]) % mod
            else:
                DP[h+1][w] += (DP[h][w]  * pattern[max(0, w - 1)] * pattern[max(0, W - w - 2)]) % mod
                DP[h+1][w] += (DP[h][w+1] * pattern[max(0, w - 1)] * pattern[max(0, W - w - 3)]) % mod
                DP[h+1][w] += (DP[h][w-1] * pattern[max(0, w - 2)] * pattern[max(0, W - w - 2)]) % mod
            DP[h+1][w] %= mod
    print(DP[H][K - 1])

    return 0

if __name__ == "__main__":
    solve()

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
print(s)
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
print(s[a][c-1]%(10**9+7)) 

a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print(s[a][c-1]%(10**9+7)) 

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
import numpy as np
H, W, K = map(int, input().split())
p = 10**9 + 7
r = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = np.zeros([H + 1, W], dtype=int)
dp[0, 0] = 1
for h in range(H):
    for w in range(W):
        if w != 0:
            dp[h+1, w] += ((dp[h, w-1] * r[w-1])%p * r[W-1-w])%p
        dp[h+1, w] = ((dp[h, w] * r[w])%p * r[W-1-w])%p
        if w != W-1:
            dp[h+1, w] += ((dp[h, w+1] * r[w])%p * r[W-2-w])%p
        dp[h+1, w] = dp[h+1, w]%p
print(dp[H, K-1])

import numpy as np
H, W, K = map(int, input().split())
p = 10**9 + 7
r = [1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = np.zeros([H + 1, W], dtype=int)
dp[0, 0] = 1
for h in range(H):
    for w in range(W):
        if w != 0:
            dp[h+1, w] += ((dp[h, w-1] * r[w-1])%p * r[W-1-w])%p
        dp[h+1, w] += ((dp[h, w] * r[w])%p * r[W-1-w])%p
        if w != W-1:
            dp[h+1, w] += ((dp[h, w+1] * r[w])%p * r[W-2-w])%p
        dp[h+1, w] = dp[h+1, w]%p
print(dp[H, K-1])

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
from collections import deque
from copy import deepcopy

H, W, K = map(int, input().split())

mod = int(1e9+7)


perm_lst = []
def bfs():
    dq = deque() 
    dq.append(([],0))
    while dq:
        post, line = dq.popleft()
        if line < W: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line))
          dq.append( (post_tmp,line+1) )
        if line < W-1: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line+1))
          dq.append( (post_tmp,line+2) )
        if line == W:
          perm_lst.append(post)
bfs()
print(perm_lst)


dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for perm in perm_lst:
    for j in range(len(perm)):
      if perm[j][0] != perm[j][1]:
        dp[i][perm[j][0]] += dp[i-1][perm[j][1]]
        dp[i][perm[j][1]] += dp[i-1][perm[j][0]]
      else:
        dp[i][perm[j][0]] += dp[i-1][perm[j][0]]
      
print(dp)

print(dp[H][K-1] % mod)

from collections import deque
from copy import deepcopy

H, W, K = map(int, input().split())

mod = int(1e9+7)


perm_lst = []
def bfs():
    dq = deque() 
    dq.append(([],0))
    while dq:
        post, line = dq.popleft()
        if line < W: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line))
          dq.append( (post_tmp,line+1) )
        if line < W-1: 
          post_tmp = deepcopy(post) 
          post_tmp.append((line,line+1))
          dq.append( (post_tmp,line+2) )
        if line == W:
          perm_lst.append(post)
bfs()
#print(perm_lst)


dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for perm in perm_lst:
    for j in range(len(perm)):
      if perm[j][0] != perm[j][1]:
        dp[i][perm[j][0]] += dp[i-1][perm[j][1]]
        dp[i][perm[j][1]] += dp[i-1][perm[j][0]]
      else:
        dp[i][perm[j][0]] += dp[i-1][perm[j][0]]
      
#print(dp)

print(dp[H][K-1] % mod)

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
MOD = 1000000007


def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W] * (H + 1)
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for k in range(1 << (W - 1)):
                ok = True
                for l in range(W - 2):
                    
                    if (k >> l) & 1 and (k >> (l + 1)) & 1:
                        ok = False

                if (ok):
                    if 1 <= j and (k >> (j - 1)) & 1:
                        dp[i + 1][j - 1] = dp[i + 1][j - 1] + dp[i][j] % MOD
                    elif j <= W and (k >> (j + 1)) & 1:
                        dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] % MOD
                    else:
                        dp[i + 1][j] = dp[i + 1][j] + dp[i][j] % MOD

    print(dp[H][K - 1])

main()


MOD = 1000000007


def main():
    H, W, K = map(int, input().split())
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for k in range(1 << (W - 1)):
                ok = True
                for l in range(W - 2):
                    
                    if (k >> l) & 1 and (k >> (l + 1)) & 1:
                        ok = False

                if (ok):
                    if 1 <= j and (k >> (j - 1)) & 1:
                        dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j]) % MOD
                    elif j <= W - 2 and (k >> j) & 1:
                        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD
                    else:
                        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD

    print(dp[H][K - 1])

main()


Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
H,W,K = map(int,input().split())
mod = 10**9+7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
dp_x = [[0,0] for i in range(W)]
dp_o = [[0,0] for i in range(W)]
dp_x[0][0] = 1
dp_x[0][1] = 1
for i in range(W-1):
    dp_x[i+1][0] = dp_x[i][0]+dp_x[i][1]
    dp_x[i+1][1] =dp_x[i][0]
dp_o[0][0] = 1
dp_o[0][1] = 0
for i in range(W-1):
    dp_o[i+1][0] = dp_o[i][0] + dp_o[i][1]
    dp_o[i+1][1] =dp_o[i][0]
dp_o = [sum(e) for e in dp_o]
dp_x = [sum(e) for e in dp_x]
dp_o = [1]+dp_o
dp_x = [1]+dp_x
if W == 1:
    print(1)
    exit()
for h in range(0,H):
    print(dp)
    for w in range(W):
        if w == 0:
            dp[h+1][0] += dp[h][0]*dp_x[W-1-1]%mod
            dp[h+1][0] += dp[h][1]*dp_o[W-1-1]%mod
        elif w == W-1:
            dp[h+1][w] += dp[h][w]*dp_x[W-1-1]%mod
            dp[h+1][w] += dp[h][w-1]*dp_o[W-1-1]%mod
        else:
            
            dp[h+1][w] += dp[h][w]*dp_x[w-1]*dp_x[W-w-2]%mod
            #right connection
            dp[h+1][w] += dp[h][w+1]*dp_x[w-1]*dp_o[W-w-2]%mod
            #left connection
            dp[h+1][w] += dp[h][w-1]*dp_o[w-1]*dp_x[W-w-2]%mod
print(dp[H][K-1]%mod)


H,W,K = map(int,input().split())
mod = 10**9+7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
dp_x = [[0,0] for i in range(W)]
dp_o = [[0,0] for i in range(W)]
dp_x[0][0] = 1
dp_x[0][1] = 1
for i in range(W-1):
    dp_x[i+1][0] = dp_x[i][0]+dp_x[i][1]
    dp_x[i+1][1] =dp_x[i][0]
dp_o[0][0] = 1
dp_o[0][1] = 0
for i in range(W-1):
    dp_o[i+1][0] = dp_o[i][0] + dp_o[i][1]
    dp_o[i+1][1] =dp_o[i][0]
dp_o = [sum(e) for e in dp_o]
dp_x = [sum(e) for e in dp_x]
dp_o = [1]+dp_o
dp_x = [1]+dp_x
if W == 1:
    print(1)
    exit()
for h in range(0,H):
    for w in range(W):
        if w == 0:
            dp[h+1][0] += dp[h][0]*dp_x[W-1-1]%mod
            dp[h+1][0] += dp[h][1]*dp_o[W-1-1]%mod
        elif w == W-1:
            dp[h+1][w] += dp[h][w]*dp_x[W-1-1]%mod
            dp[h+1][w] += dp[h][w-1]*dp_o[W-1-1]%mod
        else:
            
            dp[h+1][w] += dp[h][w]*dp_x[w-1]*dp_x[W-w-2]%mod
            #right connection
            dp[h+1][w] += dp[h][w+1]*dp_x[w-1]*dp_o[W-w-2]%mod
            #left connection
            dp[h+1][w] += dp[h][w-1]*dp_o[w-1]*dp_x[W-w-2]%mod
print(dp[H][K-1]%mod)


Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
def comb(n):
  if n % 2 == 0:
    N = n / 2
    num = 2 ** N + 2 ** N - 1
  else:
    N = ( n + 1 ) / 2
    num = 2 ** N + 2 ** ( N - 1 ) - 1
  return int(num)

d = 1000000007

h, w, k = [int(i) for i in input().split()]
kuji = [0 for i in range(w)]
kuji[0] = 1
print(kuji)
for i in range(h):

  kuji2 = [0 for i in range(w)]
  for j in range(w):
    kuji2[j] = kuji[j] * max(comb(w-(j+1)-1), 1) * max(comb(j-1), 1)
    if j >= 1:
      kuji2[j] += kuji[j-1] * max(comb(w-(j+1)-1), 1) * max(comb(j-2), 1)
    if j <= w-2:
      kuji2[j] += kuji[j+1] * max(comb(w-(j+1)-2), 1) * max(comb(j-1), 1)
  for j in range(w):
      kuji[j] = kuji2[j] 
#  print(kuji)
print(kuji[k-1] % d)

import itertools

h, w, k = [int(i) for i in input().split()]

dp = [[0 for i in range(w)] for j in range(h+1)]
dp[0][0] = 1

if w == 1:
    print(1)
    exit()

for i in range(1, h + 1):
    for kuji_list in itertools.product([0, 1], repeat = w - 1):
        for l in range(len(kuji_list)-1):
            if kuji_list[l] == 1 and kuji_list[l+1] == 1:
                break
        else:
            for j in range(w):

                if j == 0:
                    if kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                elif j == w - 1:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                else:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    elif  kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                dp[i][j] %= (10 ** 9 + 7)

ans = dp[-1][k - 1] % (10 ** 9 + 7)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] += dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]
            if col < w - 1:
                dp[row][col] += dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]
            dp[row][col] += dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]
print(dp)


h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
law = 1000000007
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] = (dp[row][col] + dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]) % law
            if col < w - 1:
                dp[row][col] = (dp[row][col] + dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]) % law
            dp[row][col] = (dp[row][col] + dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]) % law
print(dp[h][k-1])


Verdicts: Wrong Answer

Accepted
Problem: Amidakuji is a traditional method of lottery in Japan.  To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1   Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.  For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.  

Submission attempts (in order):
h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
print(fib)
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])

h,w,k=map(int,input().split())
mod=10**9+7
fib=[1,1]
for i in range(6):
  fib.append(fib[-2]+fib[-1])
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if w==1:
      dp[i+1][j]=dp[i][j]
    elif j==0:
      dp[i+1][j]=(dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
    elif j==w-1:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1])%(mod)
    else:
      dp[i+1][j]=(dp[i][j-1]*fib[j-1]*fib[w-j-1]+dp[i][j]*fib[j]*fib[w-j-1]+dp[i][j+1]*fib[j]*fib[w-j-2])%(mod)
print(dp[h][k-1])

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N and another string T of length M. These strings consist of lowercase English letters.  A string X is called a **good string** when the following conditions are all met:    * Let L be the length of X. L is divisible by both N and M.   * Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.   * Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.  Determine if there exists a good string. If it exists, find the length of the shortest such string.

Submission attempts (in order):
n, x = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(n) :
  x -= a[i]
  if(x == 0) : 
    print(i+1)
    exit()
  elif(a[i] > x) : print(i)

def gcm(a, b) :
  while(b) :
    a, b = b, a%b
  return a
def lcm(a, b) :
  return int(a*b/gcm(a, b))

n, m = map(int, input().split())
s = list(str(input()))
t = list(str(input()))
s_out = []
t_out = []
for i in range(int(gcm(n, m))) :
  s_out.append(s[i*int(n/gcm(n, m))])
for i in range(int(gcm(n, m))) :
  t_out.append(t[i*int(m/gcm(n, m))])
  
if(s_out == t_out) : print(lcm(n, m))
else : print(-1)

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N and another string T of length M. These strings consist of lowercase English letters.  A string X is called a **good string** when the following conditions are all met:    * Let L be the length of X. L is divisible by both N and M.   * Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.   * Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.  Determine if there exists a good string. If it exists, find the length of the shortest such string.

Submission attempts (in order):
def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

def lcm(m,n):
    return(m * n // gcd(m,n))

n,m = map(int,input().split())

s = input()
t = input()


g = gcd(m,n)

if(g in [n,m]):
    print(-1)
else:
    x = lcm(m,n)
    a = x // n
    b = x // m
    for i in range(x//n):
        ai = 1 + a * i
        bi = 1 + b * i
        if(s[ai] != t[bi]):
            print(-1)
            exit()
    print(lcm(m,n))

def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

def lcm(m,n):
    return(m * n // gcd(m,n))

n,m = map(int,input().split())

s = input()
t = input()


g = gcd(m,n)

if(g in [n,m]):
    print(-1)
else:
    x = lcm(m,n)
    a = x // n
    b = x // m
    for i in range(n//b):
        ai = b * i
        bi = a * i
        if(s[ai] != t[bi]):
            print(-1)
            exit()
    print(lcm(m,n))

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N and another string T of length M. These strings consist of lowercase English letters.  A string X is called a **good string** when the following conditions are all met:    * Let L be the length of X. L is divisible by both N and M.   * Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.   * Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.  Determine if there exists a good string. If it exists, find the length of the shortest such string.

Submission attempts (in order):
n,m = (int(i) for i in input().split())
s = input()
t = input()
def gcd(a,b):
	if a%b: return gcd(b,a%b)
	else: return b
g = gcd(n,m)
print(g)

n,m = (int(i) for i in input().split())
s = input()
t = input()
def gcd(a,b):
	if a%b: return gcd(b,a%b)
	else: return b
g = gcd(n,m)
ng, mg = n//g, m//g
if all(s[i*ng] == t[i*mg] for i in range(g)) :
    print(n*m//g)
else :
    print(-1)

Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N and another string T of length M. These strings consist of lowercase English letters.  A string X is called a **good string** when the following conditions are all met:    * Let L be the length of X. L is divisible by both N and M.   * Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.   * Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.  Determine if there exists a good string. If it exists, find the length of the shortest such string.

Submission attempts (in order):
import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype="int32")
P = np.ones(N + 1, dtype="int32")
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    R[n] = (R[n - 1] + rev(n)) % mod
    if n != 0:
        P[n] = P[n - 1] * n
    
C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

print(sum([a * c for a, c in zip(C, A)]) * P[N] % mod)


import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype=int)
P = np.ones(N + 1, dtype=int)
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    R[n] = (R[n - 1] + rev(n)) % mod
    if n != 0:
        P[n] = P[n - 1] * n
    
C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

print(sum([a * c for a, c in zip(C, A)]) * P[N] % mod)


N, M = map(int, input().split())
S = input()
T = input()

def f(a, b):
    if b < a:
        a, b = b, a
    
    while b % a != 0:
        a, b = b % a, a
    return a

if S[0] != T[0]:
    print(-1)

else:
    p = f(N, M)
    k = N // p
    l = M // p

    for n in range(p):
        if S[n * k] != T[n * l]:
            print(-1)
            break
    else:
        print(N * M // p)

Verdicts: Runtime Error

Runtime Error

Accepted