Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
ss, ts = input(), input()

lenS, lenT = len(ss), len(ts)

dp = [[0]*(lenT+1) for _ in range(lenS+1)]
dp[0][0] = 0
for iS, s in enumerate(ss, 1):
    for jT, t in enumerate(ts, 1):
        if s == t:
            dp[iS][jT] = dp[iS-1][jT-1] + 1
        else:
            dp[iS][jT] = max(dp[iS-1][jT], dp[iS][jT-1])

ans = ''
iS, jT = lenS, lenT
while iS*jT:
    if ss[iS-1] == ts[jT-1]:
        ans += ss[iS-1]
        iS, jT = iS-1, jT-1
    elif dp[iS-1][jT] >= dp[iS][jT-1]:
        iS -= 1
    else:
        jT -= 1

print(ans[::-1])


Fixed submission:
ss, ts = input(), input()

lenS, lenT = len(ss), len(ts)

dp = [[0]*(lenT+1) for _ in range(lenS+1)]
dp[0][0] = 0
for iS, s in enumerate(ss, 1):
    for jT, t in enumerate(ts, 1):
        if s == t:
            dp[iS][jT] = dp[iS-1][jT-1] + 1
        else:
            dp[iS][jT] = max(dp[iS-1][jT], dp[iS][jT-1])

ans = ''
iS, jT = lenS, lenT
while iS*jT:
    if ss[iS-1] == ts[jT-1]:
        ans += ss[iS-1]
        iS, jT = iS-1, jT-1
    elif dp[iS-1][jT] >= dp[iS][jT-1]:
        iS -= 1
    else:
        jT -= 1

print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ps = map(float, input().split())

dp = [0] * (N+1)
dp[0] = 1
for p in ps:
    pp = 1 - p
    for j in reversed(range(N+1)):
        dp[j] = dp[j]*pp + dp[j-1]*p

print(sum(dp[(N+1)//2:]))


Fixed submission:
N = int(input())
ps = map(float, input().split())

dp = [0] * (N+1)
dp[0] = 1
for p in ps:
    pp = 1 - p
    for j in reversed(range(N+1)):
        dp[j] = dp[j]*pp + dp[j-1]*p

print(sum(dp[(N+1)//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

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

    dp = [[0]*(N) for _ in range(N)]

    if N%2 == 1:
        for i, A in enumerate(As):
            dp[i][i] = A
    else:
        for i, A in enumerate(As):
            dp[i][i] = -A

    for W in range(2, N+1):
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = max2(As[L]+dp[L+1][R], As[R]+dp[L][R-1])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = min2(-As[L]+dp[L+1][R], -As[R]+dp[L][R-1])

    print(dp[0][N-1])


solve()


Fixed submission:
def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

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

    dp = [[0]*(N) for _ in range(N)]

    if N%2 == 1:
        for i, A in enumerate(As):
            dp[i][i] = A
    else:
        for i, A in enumerate(As):
            dp[i][i] = -A

    for W in range(2, N+1):
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = max2(As[L]+dp[L+1][R], As[R]+dp[L][R-1])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = min2(-As[L]+dp[L+1][R], -As[R]+dp[L][R-1])

    print(dp[0][N-1])


solve()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def solve():
    MOD = 10 ** 9 + 7

    def max2(x, y): return x if x >= y else y

    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [0] * (K+1)
    dp[0] = 1
    for A in As:
        accDP = [0] + list(accumulate(dp))
        accDP = [accDPi % MOD for accDPi in accDP]
        dp = [(accDP[j+1] - accDP[max2(0, j-A)]) % MOD for j in range(K+1)]

    print(dp[K])


solve()


Fixed submission:
from itertools import accumulate

MOD = 10 ** 9 + 7

N, K = map(int, input().split())
As = list(map(int, input().split()))

dp = [0] * (K+1)
dp[0] = 1
for A in As:
    accDP = [0] + list(accumulate(dp))
    accDP = [accDPi % MOD for accDPi in accDP]
    dp = [(accDP[j+1] - accDP[max(0, j-A)]) % MOD for j in range(K+1)]

print(dp[K])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

MOD = 10 ** 9 + 7

N, K = map(int, input().split())
As = list(map(int, input().split()))

dp = [0] * (K+1)
dp[0] = 1
for A in As:
    accDP = [0] + list(accumulate(dp))
    accDP = [accDPi % MOD for accDPi in accDP]
    dp = [(accDP[j+1] - accDP[max(0, j-A)]) % MOD for j in range(K+1)]

print(dp[K])


Fixed submission:
from itertools import accumulate

MOD = 10 ** 9 + 7

N, K = map(int, input().split())
As = list(map(int, input().split()))

dp = [0] * (K+1)
dp[0] = 1
for A in As:
    accDP = [0] + list(accumulate(dp))
    accDP = [accDPi % MOD for accDPi in accDP]
    dp = [(accDP[j+1] - accDP[max(0, j-A)]) % MOD for j in range(K+1)]

print(dp[K])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def solve():
    INF = 10**15

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

    accAs = list(accumulate([0]+As))

    dp = [[INF]*(N) for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for W in range(2, N+1):
        for L in range(N-W+1):
            R = L+W-1
            dp[L][R] = min([dp[L][k-1] + dp[k][R] for k in range(L+1, R+1)]) + accAs[R+1] - accAs[L]

    ans = dp[0][-1]
    print(ans)


solve()


Fixed submission:
from itertools import accumulate

INF = float('inf')

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

accAs = [0] + list(accumulate(As))

dp = [[0] * (N) for _ in range(N)]
for num in range(2, N+1):
    for i in range(N-num+1):
        cost = INF
        for j in range(1, num):
            cost = min(cost, dp[i][i+j-1] + dp[i+j][i+num-1])
        dp[i][i+num-1] = accAs[i+num] - accAs[i] + cost

print(dp[0][N-1])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

INF = float('inf')

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

accAs = [0] + list(accumulate(As))

dp = [[0] * (N) for _ in range(N)]
for num in range(2, N+1):
    for i in range(N-num+1):
        cost = INF
        for j in range(1, num):
            cost = min(cost, dp[i][i+j-1] + dp[i+j][i+num-1])
        dp[i][i+num-1] = accAs[i+num] - accAs[i] + cost

print(dp[0][N-1])


Fixed submission:
from itertools import accumulate

INF = float('inf')

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

accAs = [0] + list(accumulate(As))

dp = [[0] * (N) for _ in range(N)]
for num in range(2, N+1):
    for i in range(N-num+1):
        cost = INF
        for j in range(1, num):
            cost = min(cost, dp[i][i+j-1] + dp[i+j][i+num-1])
        dp[i][i+num-1] = accAs[i+num] - accAs[i] + cost

print(dp[0][N-1])
Buggy python submission (verdict: Runtime Error):
from collections import deque

MOD = 10**9 + 7

def rec(vNow, vPar):
    W, B = 1, 1
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        W2, B2 = rec(v2, vNow)
        W = (W * (W2+B2)) % MOD
        B = (B * W2) % MOD
    return (W, B)

N = int(input())
adjL = [[] for v in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    adjL[x-1].append(y-1)
    adjL[y-1].append(x-1)

print(sum(rec(0, -1)) % MOD)


Fixed submission:
from collections import deque

MOD = 10**9 + 7

N = int(input())
adjL = [[] for v in range(N)]
degs = [0] * N
for _ in range(N-1):
    x, y = map(int, input().split())
    adjL[x-1].append(y-1)
    adjL[y-1].append(x-1)
    degs[x-1] += 1
    degs[y-1] += 1

dpWhite = [1] * N
dpBlack = [1] * N
vNow = 0
Q = deque([v for v in range(N) if degs[v] == 1])
while Q:
    vNow = Q.popleft()
    if degs[vNow] == 0: break
    dpW, dpB = dpWhite[vNow], dpBlack[vNow]
    for v2 in adjL[vNow]:
        if degs[v2] == 0: continue
        dpWhite[v2] *= dpW + dpB
        dpWhite[v2] %= MOD
        dpBlack[v2] *= dpW
        dpBlack[v2] %= MOD
        degs[v2] -= 1
        if degs[v2] == 1:
            Q.append(v2)
    degs[vNow] = 0

print((dpWhite[vNow] + dpBlack[vNow]) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 10**9 + 7

    strN = input().rstrip()
    D = int(input())

    maxD = len(strN)

    dp = [[[0]*(D) for j in range(2)] for i in range(maxD+1)]
    dp[0][0][0] = 1
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        for isLtN in range(2):
            for modD in range(D):
                dp[d][isLtN][modD] %= MOD
                for x in range(10):
                    if not isLtN and x > Nd: continue
                    isLtN2 = isLtN or x < Nd
                    modD2 = (modD+x) % D
                    dp[d+1][isLtN2][modD2] += dp[d][isLtN][modD]

    print((dp[-1][0][0] + dp[-1][1][0] - 1) % MOD)


solve()


Fixed submission:
def solve():
    MOD = 10**9 + 7

    strN = input().rstrip()
    D = int(input())

    maxD = len(strN)

    dp = [[[0]*(D) for j in range(2)] for i in range(maxD+1)]
    dp[0][0][0] = 1
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        for isLtN in range(2):
            for modD in range(D):
                dp[d][isLtN][modD] %= MOD
                for x in range(10):
                    if not isLtN and x > Nd: continue
                    isLtN2 = isLtN or x < Nd
                    modD2 = (modD+x) % D
                    dp[d+1][isLtN2][modD2] += dp[d][isLtN][modD]

    print((dp[-1][0][0] + dp[-1][1][0] - 1) % MOD)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    scores = [0] * (1<<N)
    for S in range(1, 1<<N):
        for i in range(N):
            if (S>>i) & 1:
                score = scores[S ^ (1<<i)]
                for j in range(i+1, N):
                    if (S>>j) & 1:
                        score += Ass[i][j]
                scores[S] = score
                break

    def enumSubset(S):
        subSs = []
        subS = S
        while True:
            subSs.append(subS)
            subS = (subS-1) & S
            if subS == S:
                break
        subSs.reverse()
        return subSs

    dp = [0] * (1<<N)
    for S in range(1<<N):
        subSs = enumSubset(S)
        dp[S] = max([scores[subS] + dp[S-subS] for subS in subSs])

    print(dp[-1])


solve()


Fixed submission:
def solve():
    N = int(input())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    scores = [0] * (1<<N)
    for S in range(1, 1<<N):
        for i in range(N):
            if (S>>i) & 1:
                score = scores[S ^ (1<<i)]
                for j in range(i+1, N):
                    if (S>>j) & 1:
                        score += Ass[i][j]
                scores[S] = score
                break

    def enumSubset(S):
        subSs = []
        subS = S
        while True:
            subSs.append(subS)
            subS = (subS-1) & S
            if subS == S:
                break
        subSs.reverse()
        return subSs

    dp = [0] * (1<<N)
    for S in range(1<<N):
        subSs = enumSubset(S)
        dp[S] = max([scores[subS] + dp[S-subS] for subS in subSs])

    print(dp[-1])


solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

INF = float('inf')

L, N = map(int, input().split())
Xs = [0] + [int(input()) for _ in range(N)] + [L]

if N == 1:
    print(max(Xs[1], L - Xs[1]))
    sys.exit()

dp = [[[-INF] * (2) for B in range(N+1)] for A in range(N+1)]
dp[1][N][0] = 0
dp[1][N][1] = 0
for A in range(1, N+1):
    for B in reversed(range(A, N+1)):
        # C=0 ccw
        C = 0
        if B > 1:  # ccw
            dp[A][B-1][0] = max(dp[A][B-1][0], dp[A][B][C] + Xs[B+1] - Xs[B])
        if A < N:  # cw
            dp[A+1][B][1] = max(dp[A+1][B][1], dp[A][B][C] + (L - Xs[B+1]) + Xs[A])
        # C=1 cw
        C = 1
        if B > 1:  # ccw
            dp[A][B-1][0] = max(dp[A][B-1][0], dp[A][B][C] + Xs[A-1] + (L - Xs[B]))
        if A < N:  # cw
            dp[A+1][B][1] = max(dp[A+1][B][1], dp[A][B][C] + Xs[A] - Xs[A-1])

ans = 0
for A in range(N+1):
    for B in range(N+1):
        for C in range(2):
            ans = max(ans, dp[A][B][C])
print(ans)


Fixed submission:
from itertools import accumulate

def getRangeSum(accXs, iFr, iTo):
    return accXs[iTo+1] - accXs[iFr]

def getAns(accXs, accRevXs, Xs, revXs):
    ans = 0
    for i in range(N):
        num = (N-i)//2
        dist = 2 * getRangeSum(accXs, i, i + num-1)
        dist += 2 * getRangeSum(accRevXs, 0, num-1)
        if (N-i)%2 == 0:
            dist -= revXs[num-1]
        else:
            dist += Xs[i + num]
        ans = max(ans, dist)
    return ans

L, N = map(int, input().split())
Xs = [int(input()) for _ in range(N)]

revXs = [L-X for X in reversed(Xs)]
accXs = [0] + list(accumulate(Xs))
accRevXs = [0] + list(accumulate(revXs))

print(max(getAns(accXs, accRevXs, Xs, revXs), getAns(accRevXs, accXs, revXs, Xs)))
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil, log2

def max2(x, y): return x if x >= y else y

def getNums(As, N):
    dp = list(range(16))
    nums = [0] * N
    for i in reversed(range(N - 1)):
        dx = ceil( log2( As[i] / As[i+1] ) / 2 )
        dp2 = [0] * 16
        for x in range(16):
            nx = x + dx
            if nx <= 15:
                dp2[x] = dp[max2(0, nx)] + x
            else:
                dp2[x] = dp[15] + x + (N - 1 - i) * (nx - 15)
        dp = dp2
        nums[i] = dp[0]
    return nums

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

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)


Fixed submission:
from math import floor, ceil, log2

def getNums(As, N):
    nums = [0] * N
    accNum = 0
    stack = [(N-1, float('inf'))]
    dNow = 0
    for i in reversed(range(N - 1)):
        if As[i] <= As[i+1]:
            dd = floor( log2( As[i+1] / As[i] ) / 2 )
            if dd > 0: stack.append((i, dNow))
            dNow -= dd
        else:
            dTgt = dNow + ceil( log2( As[i] / As[i+1] ) / 2 )
            while dNow < dTgt:
                pos, d = stack[-1]
                if dTgt > d:
                    accNum += (d - dNow) * (pos - i)
                    dNow = d
                    stack.pop()
                else:
                    accNum += (dTgt - dNow) * (pos - i)
                    if dTgt == d: stack.pop()
                    dNow = dTgt
                    break
        nums[i] = accNum
    return nums

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

numPstvs = getNums(As, N)
numNgtvs = getNums(As[::-1], N)[::-1]

ans = float('inf')
for i, (p, m) in enumerate(zip(numPstvs + [0], [0] + numNgtvs)):
    ans = min(ans, 2 * p + 2 * m + i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(58):
    Ps.append(Ps[-1] * 2)
Ps = Ps[::-1]

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)


Fixed submission:
from collections import Counter

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

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(58):
    Ps.append(Ps[-1] * 2)
Ps = Ps[::-1]

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# numChar種類で条件を満たせるかを判定する
def check(As, numChar):
    Ss = [(-1, -1)]
    APrev = As[0]
    for A in As[1:]:
        if APrev >= A: # 文字列長が同じor短くなる場合
            if numChar == 1: return False
            # A文字目より後ろを削除する
            while Ss[-1][0] > A:
                Ss.pop()
            # A文字目を[+1]する
            posS = A
            while Ss[-1] == (posS, numChar - 1):
                Ss.pop()
                posS -= 1
            if posS == 0:
                return False
            elif Ss[-1][0] == posS:
                Ss[-1] = (posS, Ss[-1][1] + 1)
            else:
                Ss.append((posS, 1))
        APrev = A
    return True

# 条件を満たす最小のnumCharを二分探索する
def solve(As, N):
    lft, rgt = 0, N
    while rgt - lft > 1:
        mid = (lft + rgt) // 2
        isOK = check(As, mid)
        if isOK:
            rgt = mid
        else:
            lft = mid
    return rgt

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

print(solve(As, N))


Fixed submission:
# numChar種類で条件を満たせるかを判定する
def check(As, numChar):
    Ss = [(-1, -1)]
    APrev = As[0]
    for A in As[1:]:
        if APrev >= A: # 文字列長が同じor短くなる場合
            if numChar == 1: return False
            # A文字目より後ろを削除する
            while Ss[-1][0] > A:
                Ss.pop()
            # A文字目を[+1]する
            posS = A
            while Ss[-1] == (posS, numChar - 1):
                Ss.pop()
                posS -= 1
            if posS == 0:
                return False
            elif Ss[-1][0] == posS:
                Ss[-1] = (posS, Ss[-1][1] + 1)
            else:
                Ss.append((posS, 1))
        APrev = A
    return True

# 条件を満たす最小のnumCharを二分探索する
def solve(As, N):
    lft, rgt = 0, N
    while rgt - lft > 1:
        mid = (lft + rgt) // 2
        isOK = check(As, mid)
        if isOK:
            rgt = mid
        else:
            lft = mid
    return rgt

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

print(solve(As, N))
Buggy python submission (verdict: Runtime Error):
H, W, N = map(int, input().split())
posObss = [{H} for y in range(W)]
for _ in range(N):
    X, Y = map(int, input().split())
    posObss[Y - 1].add(X - 1)

ans = H
xNow = 0
for y in range(W):
    xLim = min([x for x in posObss[y] if x > xNow])
    ans = min(ans, xLim)

    xNow += 1
    while xNow in posObss[y + 1]:
        xNow += 1
    if xNow >= xLim: break

print(ans)


Fixed submission:
H, W, N = map(int, input().split())
posObss = [{H} for y in range(W)]
for _ in range(N):
    X, Y = map(int, input().split())
    posObss[Y - 1].add(X - 1)

ans = H
xNow = 0
for y in range(W):
    xLim = min([x for x in posObss[y] if x > xNow])
    ans = min(ans, xLim)

    if y == W - 1: break
    xNow += 1
    while xNow in posObss[y + 1]:
        xNow += 1
    if xNow >= xLim: break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

N, K = map(int, input().split())
As = list(map(int, input().split()))

accAs = [0] + list(accumulate(As))

Bs = []
for L in range(N):
    for R in range(L, N):
        Bs.append(accAs[R + 1] - accAs[L])

ans = 0
for d in reversed(range(50)):
    num = sum([(B >> d) & 1 for B in Bs])
    if num >= K:
        ans += 1 << d
        Bs = [B if (B >> d) & 1 else 0 for B in Bs]

print(ans)


Fixed submission:
from itertools import accumulate

N, K = map(int, input().split())
As = list(map(int, input().split()))

accAs = [0] + list(accumulate(As))

Bs = []
for L in range(N):
    for R in range(L, N):
        Bs.append(accAs[R + 1] - accAs[L])

ans = 0
for d in reversed(range(40)):
    num = sum([(B >> d) & 1 for B in Bs])
    if num >= K:
        ans += 1 << d
        Bs = [B for B in Bs if (B >> d) & 1]

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
As = [int(input()) for _ in range(N)]

As.sort()
#print(As)

def f(As):
    Bs = [0] * N
    iB = N // 2
    d = -2
    for A in As[:N//2]:
    #    print(A, iB, d)
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d - 2
        else:
            d = -d + 2
#    print(Bs)

    if N % 2:
        iB = N // 2 + 1
        d = -2
    else:
        iB = N // 2 - 1
        d = +2
    for A in reversed(As[N//2:]):
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d - 2
        else:
            d = -d + 2
#    print(Bs)

    ans = 0
    for i in range(N - 1):
        ans += abs(Bs[i + 1] - Bs[i])
#    print(ans)
    return ans

print(max(f(As), f(As[::-1])))


Fixed submission:
N = int(input())
As = [int(input()) for _ in range(N)]

As.sort(reverse=True)

if N % 2:
    ans = 2 * sum(As[:N//2 - 1]) - 2 * sum(As[N//2 + 2:])
    A1, A2, A3 = As[N//2 - 1:N//2 + 2]
    ans += max(A1 + A2 - 2*A3, 2*A1 - A2 - A3)
else:
    ans = 2 * sum(As[:N//2 - 1]) + As[N//2 - 1] - As[N//2] - 2 * sum(As[N//2 + 1:])

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

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

parities = [(X+Y) % 2 for X, Y in XYs]
if len(set(parities)) != 1:
    print(-1)
    sys.exit()

m = 19 if parities[0] else 20
ds = [1] * m
print(m)
print(*ds)

for X, Y in XYs:
    if X >= 0:
        ws = ['R'] * X
    else:
        ws = ['L'] * -X
    if Y >= 0:
        ws += ['U'] * Y
    else:
        ws += ['D'] * -Y
    ws += ['RL'] * ((m-abs(X)-abs(Y)) // 2)
    print(''.join(ws))


Fixed submission:
import sys

LEN_D = 31
CONST = 2**LEN_D - 1

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

parities = [(X+Y) % 2 for X, Y in XYs]
if len(set(parities)) != 1:
    print(-1)
    sys.exit()

if parities[0]:
    m = LEN_D
    ds = [2**i for i in range(LEN_D)]
else:
    m = LEN_D + 1
    ds = [1] + [2**i for i in range(LEN_D)]
print(m)
print(*ds)

for X, Y in XYs:
    ws = []
    if (X+Y) % 2 == 0:
        X -= 1
        ws.append('R')
    u = ((X+Y) + CONST) // 2
    v = ((X-Y) + CONST) // 2
    for i in range(LEN_D):
        ws.append('LDUR'[((u>>i) & 1) * 2 + ((v>>i) & 1)])
    print(''.join(ws))
Buggy python submission (verdict: Runtime Error):
from math import floor, sqrt
from collections import Counter

MOD = 10 ** 9 + 7

# xを素因数分解する
def getPrimeFactor(x):
    ans = []
    for d in range(2, floor(sqrt(x)) + 1):
        while x % d == 0:
            ans.append(d)
            x //= d

    if x != 1:
        ans.append(x)

    return ans

# xのn乗（二分累乗法）
def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans


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

PFs = getPrimeFactor(M)
cnt = Counter(PFs)

maxNum = max(cnt.values())
N2 = N + maxNum

# facts[x]: xの階乗
facts = [1] + [0] * N2
for x in range(1, N2 + 1):
    facts[x] = (facts[x - 1] * x) % MOD

# invFs[x]: xの階乗の逆元
invFs = [0] * N2 + [power(facts[N2], MOD - 2)]
for x in reversed(range(N2)):
    invFs[x] = (invFs[x + 1] * (x + 1)) % MOD

def comb(n, k):
    return ((facts[n] * invFs[k]) % MOD * invFs[n - k]) % MOD


ans = 1
for num in cnt.values():
    ans = (ans * comb(N + num - 1, num)) % MOD
print(ans)


Fixed submission:
from math import floor, sqrt
from collections import Counter

MOD = 10 ** 9 + 7

# xを素因数分解する
def getPrimeFactor(x):
    ans = []
    for d in range(2, floor(sqrt(x)) + 1):
        while x % d == 0:
            ans.append(d)
            x //= d

    if x != 1:
        ans.append(x)

    return ans

# xのn乗（二分累乗法）
def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans


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

PFs = getPrimeFactor(M)
cnt = Counter(PFs)

N2 = N
if len(cnt):
    N2 += max(cnt.values())

# facts[x]: xの階乗
facts = [1] + [0] * N2
for x in range(1, N2 + 1):
    facts[x] = (facts[x - 1] * x) % MOD

# invFs[x]: xの階乗の逆元
invFs = [0] * N2 + [power(facts[N2], MOD - 2)]
for x in reversed(range(N2)):
    invFs[x] = (invFs[x + 1] * (x + 1)) % MOD

def comb(n, k):
    return ((facts[n] * invFs[k]) % MOD * invFs[n - k]) % MOD


ans = 1
for num in cnt.values():
    ans = (ans * comb(N + num - 1, num)) % MOD
print(ans)