Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        B = [0 for _ in range(N)]
        count = 0
        for i in range(N):
            if A[i] == N:
                count += 1
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])
            B[l] += 1
            if r + 1 < N:
                B[r + 1] -= 1
        B = list(accumulate(B))
        if count == N:
            break
        else:
            A = B
    print(*B, sep=" ")


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        B = [0 for _ in range(N)]
        count = 0
        for i in range(N):
            if A[i] == N:
                count += 1
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])
            B[l] += 1
            if r + 1 < N:
                B[r + 1] -= 1
        B = list(accumulate(B))
        if count == N:
            break
        else:
            A = B
    print(*B, sep=" ")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = 10 ** 18


def main():
    N = int(input())
    A = list(map(int, input().split()))
    answer = 1
    for i in range(N):
        answer *= A[i]

    if answer > INF:
        print(-1)
    else:
        print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = 10 ** 18


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return

    answer = 1
    for i in range(N):
        answer *= A[i]
        if answer > INF:
            print(-1)
            return

    print(answer)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    went = [0] * N
    went[0] = 1
    Flag = True
    check = [0]
    cnt = 1
    now = 0
    while Flag and (cnt <= K):
        now = A[now] - 1
        if went[now] == 1:
            ind = check.index(now) - 1
            cnt = cnt - ind - 1
            Flag = False
        else:
            check.append(now)
            went[now] = 1
            cnt += 1
            continue
    if len(check) >= K:
        print(check[K] + 1)
    else:
        K = (K - ind) % cnt
        print(check[ind + K] + 1)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    went = [0] * N
    went[0] = 1
    Flag = True
    check = [0]
    cnt = 1
    now = 0
    while Flag and (cnt <= K + 1):
        now = A[now] - 1
        if went[now] == 1:
            ind = check.index(now)
            if ind == 0:
                cnt = len(check)
            else:
                cnt = len(check) - ind

            Flag = False
        else:
            check.append(now)
            went[now] = 1
            cnt += 1
            continue

    if len(check) > K:
        print(check[K] + 1)
    else:
        if ind == 0:
            K = K % cnt
            print(check[K] + 1)
        else:
            ind -= 1
            K = (K - ind - 1) % cnt
            print(check[ind + K + 1] + 1)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    answer = 0
    for i in range(N):
        for j in range(i + A[i] + 1, N):
            if A[i] + A[j] == j - i:
                answer += 1
    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = defaultdict(list)
    R = defaultdict(list)
    for i in range(N):
        L[A[i] + i].append(i)
        R[i - A[i]].append(i)
    K = list(L.keys())

    answer = 0
    for k in K:
        l = len(L[k])
        r = len(R[k])
        answer += l * r
    print(answer)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7


def main():
    S = input()
    answer = 0
    for i in range(len(S)):
        func = lambda x, y: (int(x) * 10 + int(y)) % 2019
        A = list(accumulate(S[i:], func, initial=0))
        answer += A.count(0) - 1
    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    S = list(input())
    N = len(S)
    check = [0] * 2019
    ten = 1
    mod = 1
    check[mod] += 1
    for i in range(N):
        mod = (mod + int(S[N - i - 1]) * ten) % 2019
        ten = (ten * 10) % 2019
        check[mod] += 1
    answer = 0
    for i in range(2019):
        answer += ((check[i] - 1) * check[i]) // 2
    print(answer)


if __name__ == "__main__":
    main()

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


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7


def main():
    S = input()
    answer = 0
    for i in range(len(S)):
        func = lambda x, y: (int(x) * 10 + int(y)) % 2019
        A = list(accumulate(S[i:], func, initial=0))
        answer += A.count(0) - 1
    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    S = list(input())
    N = len(S)
    check = [0] * 2019
    ten = 1
    mod = 1
    check[mod] += 1
    for i in range(N):
        mod = (mod + int(S[N - i - 1]) * ten) % 2019
        ten = (ten * 10) % 2019
        check[mod] += 1
    answer = 0
    for i in range(2019):
        answer += ((check[i] - 1) * check[i]) // 2
    print(answer)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    List = np.unique(A)
    count = np.bincount(A)
    # print(count)

    dic = {}
    Ans = 0
    for l in List:
        n = count[l]
        num = n * (n - 1) // 2
        Ans += num
        dic[l] = num
    B = np.empty(N, dtype=np.int)
    for l in List:
        n = count[l] - 1
        num = n * (n - 1) // 2
        B = np.where(A == l, int(Ans - dic[l] + num), B)
    print(*B, sep="\n")


main()


Fixed submission:
import sys
import numpy as np


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    count = np.bincount(A)
    # print(count)
    total = (count * (count - 1)).sum() // 2
    answer = (total - (count - 1))[A]
    print("\n".join(answer.astype(str)))


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    List = np.unique(A)
    count = np.bincount(A)

    dic = {}
    Ans = 0
    for l in List:
        n = count[l]
        num = n * (n - 1) // 2
        Ans += num
        dic[l] = num

    for i in range(N):
        n = count[A[i]] - 1
        num = n * (n - 1) // 2
        answer = Ans - dic[A[i]] + num
        print(answer)


main()


Fixed submission:
import sys
import numpy as np


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    count = np.bincount(A)
    # print(count)
    total = (count * (count - 1)).sum() // 2
    answer = (total - (count - 1))[A]
    print("\n".join(answer.astype(str)))


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import permutations


def input():
    return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())

    S = [list(input()) for _ in range(H)]
    C = [2 * i for i in range(H - 1)] + [2 * j + 1 for j in range(W - 1)]
    check = list(permutations(C))
    answer = float("inf")
    for chk in check:
        if S[0][0] == "#":
            cnt = 1
        else:
            cnt = 0
        now = [0, 0]
        for i in range(H + W - 2):
            if chk[i] % 2 == 0:
                now[0] += 1
            else:
                now[1] += 1
            if now[0] <= H - 1 and now[1] <= W - 1:
                if S[now[0]][now[1]] == "#":
                    cnt += 1
            # print(now)
            # print(cnt)
        if cnt < answer:
            answer = cnt
    print(answer)


main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())

    S = [list(input()) for _ in range(H)]
    # print(S)
    check = [[10 ** 9 for i in range(W)] for j in range(H)]
    if S[0][0] == "#":
        check[0][0] = 1
    else:
        check[0][0] = 0
    for i in range(1, W):
        left = check[0][i - 1]
        if S[0][i] == "#":
            if S[0][i - 1] == "#":
                check[0][i] = left
            else:
                check[0][i] = left + 1
        else:
            check[0][i] = left
    for i in range(1, H):
        up = check[i - 1][0]
        if S[i][0] == "#":
            if S[i - 1][0] == "#":
                check[i][0] = up
            else:
                check[i][0] = up + 1
        else:
            check[i][0] = up
    for i in range(1, H):
        for j in range(1, W):
            # print(S[i][j])
            left = check[i][j - 1]
            up = check[i - 1][j]
            if S[i][j] == "#":
                if S[i][j - 1] == "#" and S[i - 1][j] == "#":
                    check[i][j] = min(left, up)
                elif S[i][j - 1] != "#" and S[i - 1][j] == "#":
                    check[i][j] = min(left + 1, up)
                elif S[i][j - 1] == "#" and S[i - 1][j] != "#":
                    check[i][j] = min(left, up + 1)
                else:
                    check[i][j] = min(left, up) + 1
            else:
                check[i][j] = min(left, up)
    # print(check)
    print(check[-1][-1])


main()
Buggy python submission (verdict: Runtime Error):
from decimal import Decimal

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


A = Decimal(a) ** (1 / 2) + Decimal(b) ** (1 / 2)
C = Decimal(c) ** (1 / 2)
if A < C:
    print("Yes")
else:
    print("No")


Fixed submission:
from decimal import Decimal

a, b, c = map(int, input().split())
k = Decimal(0.5)

A = Decimal(a) ** k + Decimal(b) ** k
C = Decimal(c) ** k
if A < C:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = {
    1: ["a"],
    2: ["aa", "ab"],
    3: ["aaa", "aab", "aba", "abb", "abc"],
    4: [
        "aaaa",
        "aaab",
        "aabb",
        "aabc",
        "abaa",
        "abab",
        "abac",
        "abba",
        "abbb",
        "abbc",
        "abca",
        "abcb",
        "abcc",
        "abcd",
    ],
    5: [
        "aaaaa",
        "aaaab",
        "aaaba",
        "aaabb",
        "aaabc",
        "aabba",
        "aabbb",
        "aabbc",
        "aabca",
        "aabcb",
        "aabcc",
        "aabcd",
        "abaaa",
        "abaab",
        "abaac",
        "ababa",
        "ababb",
        "ababc",
        "abaca",
        "abacb",
        "abacc",
        "abacd",
        "abbaa",
        "abbab",
        "abbac",
        "abbba",
        "abbbb",
        "abbbc",
        "abbca",
        "abbcb",
        "abbcc",
        "abbcd",
        "abcaa",
        "abcab",
        "abcac",
        "abcad",
        "abcba",
        "abcbb",
        "abcbc",
        "abcbd",
        "abcca",
        "abccb",
        "abccc",
        "abccd",
        "abcda",
        "abcdb",
        "abcdc",
        "abcdd",
        "abcde",
    ],
}
Ans = A[N]
for i in range(len(Ans)):
    print(Ans[i])


Fixed submission:
N = int(input())
D = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
Ans = [["a"]]
for i in range(1, 10):
    before = Ans[i - 1]
    # print(before)
    next = []
    for j in before:
        L = set(list(j))
        # print(L)
        for k in range(len(L) + 1):
            # print(j)
            next.append(j + D[k])
    Ans.append(next)
# print(Ans)
print(*Ans[N - 1], sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
Left = True

for i in range(Q):
    TFC = input()

    if TFC[0] == "1":
        Left = not Left

    elif TFC[0] == "2" and TFC[2] == "1":
        if Left:
            S = TFC[4] + S
        else:
            S = S + TFC[4]

    else:
        if Left:
            S = S + TFC[4]
        else:
            S = TFC[4] + S

if not Left:
    S = S[::-1]

print(S)


Fixed submission:
from collections import deque

S = deque(map(str, input().split()))
Q = int(input())
Left = False

for i in range(Q):
    TFC = input()

    if TFC[0] == "1":
        Left = not Left

    else:
        _, f, c = TFC[0], TFC[2], TFC[4]
        f = int(f)
        if Left ^ (f == 1):
            S.appendleft(c)

        else:
            S.append(c)

T = "".join(S)
if Left:
    T = T[::-1]

print(T)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = sorted(list(map(int, input().split())))
if N == 1:
    print(0)
else:
    r = X[-1] - X[0]
    ans = float("inf")
    if r == 0:
        print(0)
    else:
        for i in range(r):
            R = X[0] + i
            hp = 0
            for j in range(N):
                hp = hp + (R - X[j]) ** 2
 
            ans = min(hp, ans)
 
    print(ans)
N = int(input())
X = sorted(list(map(int, input().split())))
if N == 1:
    print(0)
else:
    r = X[-1] - X[0]
    ans = float("inf")
    for i in range(r+1):
      R = X[0] + i
      hp = 0
      for j in range(N):
        hp = hp + (R - X[j]) ** 2

        ans = min(hp, ans)

    print(ans)
提出情報


Fixed submission:
import numpy as np

N = int(input())
X = np.array(list(map(int, input().split())))
costs = []
for i in range(101):
    costs.append(np.sum((X - i) ** 2))
print(min(costs))

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
X = np.array(list(map(int, input().split())))
cost = float("inf")
for i in range(101):
    cost = min(np.sum((X - i) ** 2))
print(cost)

Fixed submission:
import numpy as np

N = int(input())
X = np.array(list(map(int, input().split())))
costs = []
for i in range(101):
    costs.append(np.sum((X - i) ** 2))
print(min(costs))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
K = sorted([kv[0] for kv in L.items() if kv[1] == max(L.values())])

for i in range(len(K)):
    print(K[i])


Fixed submission:
from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = [input() for i in range(n)]
ss = sorted(list(set(S)))
L = {}
for i in ss:
    L[i] = S.count(i)

K = sorted([kv[0] for kv in L.items() if kv[1] == max(L.values())])
for i in range(len(K)):
    print(K[i])


Fixed submission:
from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = {}
for i in range(n):
    s = input()
    if s in S:
        S[s] += 1
    else:
        S[s] = 1

L = sorted([kv[0] for kv in S.items() if kv[1] == max(S.values())])
for i in range(len(L)):
    print(L[i])


Fixed submission:
from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")
Buggy python submission (verdict: Runtime Error):
n = str(input())[::-1]
n = "0" + n
l = len(n)
ans = 0
flg = 0
check = 0

for i in range(l):
    check = int(n[i])
    check += flg
    if check == 5:
        if int(n[i + 1]) >= 5:
            ans += 5
            flg = 1
        else:
            ans += 5
            flg = 0
    elif check > 5:
        ans += 10 - check
        flg = 1
    else:
        ans += check
        flg = 0
print(ans + flg)



Fixed submission:
n = str(input())[::-1]
n = n + "0"
l = len(n)
ans = 0
flg = 0
check = 0

for i in range(l):
    check = int(n[i])
    check += flg
    if check == 5:
        if int(n[i + 1]) >= 5:
            ans += 5
            flg = 1
        else:
            ans += 5
            flg = 0
    elif check > 5:
        ans += 10 - check
        flg = 1
    else:
        ans += check
        flg = 0
print(ans + flg)

Buggy python submission (verdict: Runtime Error):
n = input()
l = len(n)
n = int(n)
ans = 0


def c(l, n, ans):

    a = n // (10 ** (l - 1))
    if l == 1:
        if a <= 5:
            return ans + a
        else:
            return ans + 1 + (10 - a)
    elif a == 5 and l > 1:
        if (n // (10 ** (l - 2))) % 10 <= 4:
            return c(l - 1, n % (10 ** (l - 1)), ans + a)
        else:
            return c(l, 10 ** l - n, ans + 1)
    elif a <= 4 and l > 1:
        return c(l - 1, n % (10 ** (l - 1)), ans + a)
    else:
        return c(l, 10 ** l - n, ans + 1)


print(c(l, n, ans))


Fixed submission:
n = str(input())[::-1]
n = n + "0"
l = len(n)
ans = 0
flg = 0
check = 0

for i in range(l):
    check = int(n[i])
    check += flg
    if check == 5:
        if int(n[i + 1]) >= 5:
            ans += 5
            flg = 1
        else:
            ans += 5
            flg = 0
    elif check > 5:
        ans += 10 - check
        flg = 1
    else:
        ans += check
        flg = 0
print(ans + flg)

Buggy python submission (verdict: Runtime Error):
n = input()
l = len(n)
n = int(n)
ans = 0


def c(l, n, ans):
    print(ans)
    a = n // (10 ** (l - 1))
    if l == 1:
        if a <= 5:
            return ans + a
        else:
            return ans + 1 + (10 - a)
    elif a == 5 and l > 1:
        if (n // (10 ** (l - 2))) % 10 <= 4:
            return c(l - 1, n % (10 ** (l - 1)), ans + a)
        else:
            return c(l, 10 ** l - n, ans + 1)
    elif a <= 4 and l > 1:
        return c(l - 1, n % (10 ** (l - 1)), ans + a)
    else:
        return c(l, 10 ** l - n, ans + 1)


print(c(l, n, ans))


Fixed submission:
n = str(input())[::-1]
n = n + "0"
l = len(n)
ans = 0
flg = 0
check = 0

for i in range(l):
    check = int(n[i])
    check += flg
    if check == 5:
        if int(n[i + 1]) >= 5:
            ans += 5
            flg = 1
        else:
            ans += 5
            flg = 0
    elif check > 5:
        ans += 10 - check
        flg = 1
    else:
        ans += check
        flg = 0
print(ans + flg)
Buggy python submission (verdict: Runtime Error):
s,t=map(str,input().spilt())
a,b=map(int,input().split())
u=input()
if u==s:
  print(str(a-1),str(b))
else:
  print(str(a),str(b-1))

Fixed submission:
s, t = map(str, input().split())
a, b = map(int,input().split())
u = input()

if u==s:
    print(a-1, b)

else:
    print(a, b-1)

Buggy python submission (verdict: Runtime Error):
s,t=map(str,input().spilt())
a,b=map(int,input().split())
u=input()
if u==s:
  print(a-1,b)
else:
  print(a,b-1)

Fixed submission:
s, t = map(str, input().split())
a, b = map(int,input().split())
u = input()

if u==s:
    print(a-1, b)

else:
    print(a, b-1)

Buggy python submission (verdict: Runtime Error):
s,t=map(str,input().spilt())
a,b=map(int,input().split())
u=input()
if u==s:
  print(s-1,t)
else:
  print(s,t-1)

Fixed submission:
s, t = map(str, input().split())
a, b = map(int,input().split())
u = input()

if u==s:
    print(a-1, b)

else:
    print(a, b-1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int,input().split())
P = list(map(int,input().split()))
S = []

for i in range(n-k+1):
    S.append(sum(P[i:i+k]))

print((max(S)+k)/2)

Fixed submission:
from itertools import accumulate
n, k = map(int,input().split())
P = list(map(lambda x:(int(x)+1)/2,input().split()))
A = list(accumulate([0]+P))
B = []
for i in range(n-k+1):
    B.append(A[i+k]-A[i])

print(max(B))

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int,input().split())
P = list(map(lambda x:(int(x)+1)/2,input().split()))
S = []

for i in range(n-k+1):
    S.append(sum(P[i:i+k]))

print(max(S))

Fixed submission:
from itertools import accumulate
n, k = map(int,input().split())
P = list(map(lambda x:(int(x)+1)/2,input().split()))
A = list(accumulate([0]+P))
B = []
for i in range(n-k+1):
    B.append(A[i+k]-A[i])

print(max(B))
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    d_0 = [N for _ in range(61)]
    d_1 = [0 for _ in range(61)]
    max_d = 0
    for a in A:
        d = 0
        while a > 0:
            keta = a % 2
            a //= 2
            if keta == 1:
                d_0[d] -= 1
                d_1[d] += 1
            d += 1
        if d > max_d:
            max_d = d
    # print(d_0)
    # print(d_1)
    answer = 0
    for i in range(max_d):
        answer += d_0[i] * d_1[i] * 2 ** i
        answer %= MOD
    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    d_0 = [N for _ in range(61)]
    d_1 = [0 for _ in range(61)]
    max_d = 0
    for a in A:
        d = 0
        while a > 0:
            keta = a % 2
            a //= 2
            if keta == 1:
                d_0[d] -= 1
                d_1[d] += 1
            d += 1
        if d > max_d:
            max_d = d
    # print(d_0)
    # print(d_1)
    answer = 0
    for i in range(max_d):
        answer += d_0[i] * d_1[i] * 2 ** i
        answer %= MOD
    print(answer)


if __name__ == "__main__":
    main()