Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
C = [int(input()) for _ in range(N)]
C = C[::-1]
mod = 10 ** 9 + 7

newC = []
while C:
    c = C.pop()
    if not newC or newC[-1] != c:
        newC.append(c)
N = len(newC)

seen = [0] * (10 ** 5 + 10)
dp = [0] * (N + 1)
dp[0] = 1
seen[newC[0]] = 1

for i, c in enumerate(newC[1:], start=1):
    cnt = seen[c]
    seen[c] = (seen[c] + dp[i - 1]) % mod
    dp[i] = (dp[i - 1] + cnt) % mod

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


Fixed submission:
from collections import defaultdict
N = int(input())
tmp = [int(input()) for _ in range(N)]
mod = 10 ** 9 + 7
C = []
for c in tmp:
    if not C:
        C.append(c)
        continue
    if C[-1] != c:
        C.append(c)
N = len(C)

last = defaultdict(int)
ans = 1

for c in C:
    ans += last[c]
    ans %= mod
    last[c] = ans

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
yen=[]
hon=[]
for i in range(N):
    a,b=map(int,input().split())
    yen.append(a)
    hon.append(b)

loop=True
pay=0

while loop:
    mise=yen.index(min(yen))
    value=yen[mise]
    stock=hon[mise]
    if M>stock:
        pay+=stock*value
    else:
        pay+=M*value
    M-=stock
    del yen[mise]
    del hon[mise]

    if M<=0:
        loop=False

print(pay)

Fixed submission:
N,M=map(int,input().split())
mises=[]
for i in range(N):
    mises.append(list(map(int,input().split())))

mises.sort()
pay=0
for i in mises:
    if i[1]<M:
        pay+=i[0]*i[1]
        M-=i[1]
    else:
        pay+=i[0]*M
        break
print(pay)
Buggy python submission (verdict: Runtime Error):
s=input()
lis=[]
n=1
output=0
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        lis.append(n)
        n=1
    else:
        n+=1

    if i==len(s)-2:
        lis.append(n)
#print(lis)
if len(lis)==1:
    output=0
else:
    loop=True
    while loop:
        a=lis[0]
        b=lis[1]
        if a==b:
            output+=a+b
            del lis[0]
            del lis[0]
        elif a<b and len(lis)>2:
            output+=a*2
            lis[1]-=a
            del lis[0]
        elif a>b and len(lis)>2:
            output+=b*2
            lis[2]+=a-b
            del lis[0]
            del lis[0]
        elif len(lis)<=2:
            output+=min(a,b)*2
            del lis[0]

        if len(lis)==0 or len(lis)==1:
            loop=False

print(output)
    
            


Fixed submission:
s=input()
n0=0
n1=0
for i in s:
    if i=="0":
        n0+=1
    else:
        n1+=1
print(2*min(n0,n1))

Buggy python submission (verdict: Runtime Error):
s=input()
lis=[]
n=1
output=0
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        lis.append(n)
        n=1
    else:
        n+=1

    if i==len(s)-2:
        lis.append(n)
#print(lis)

loop=True
while loop:
    a=lis[0]
    b=lis[1]
    if a==b:
        output+=a*2
        del lis[0]
        del lis[0]
    elif a<b:
        output+=a*2
        lis[1]-=a
        del lis[0]
    elif a>b:
        if len(lis)<2:
            output+=b*2
            loop=False
        else:
            lis[2]+=abs(b-a)
            output+=b*2
            del lis[0]
            del lis[0]
    if len(lis)==0 or len(lis)==1:
        loop=False
print(output)
    


Fixed submission:
s=input()
n0=0
n1=0
for i in s:
    if i=="0":
        n0+=1
    else:
        n1+=1
print(2*min(n0,n1))

Buggy python submission (verdict: Runtime Error):
s=input()
lis=[]
n=1
output=0
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        lis.append(n)
        n=1
    else:
        n+=1

    if i==len(s)-2:
        lis.append(n)
print(lis)

loop=True
while loop:
    a=lis[0]
    b=lis[1]
    if a==b:
        output+=a*2
        del lis[0]
        del lis[0]
    elif a<b:
        output+=a*2
        lis[1]-=a
        del lis[0]
    elif a>b:
        if len(lis)<2:
            output+=b*2
            loop=False
        else:
            lis[2]+=abs(b-a)
            output+=b*2
            del lis[0]
            del lis[0]
    if len(lis)==0 or len(lis)==1:
        loop=False
print(output)
    
            



Fixed submission:
s=input()
n0=0
n1=0
for i in s:
    if i=="0":
        n0+=1
    else:
        n1+=1
print(2*min(n0,n1))
Buggy python submission (verdict: Runtime Error):
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

inf = 10**18
dp = [-inf]*(N+1)
dp[0] = 0


for a in A:
    for j in range(d[a], N + 1):
        dp[j] = max(dp[j], dp[j - d[a]] + 1)

ans = ""
remain = dp[N]
match = N
while match > 0:
    for a in A:
        if dp[match - d[a]] == remain - 1:
            ans += str(a)
            match -= d[a]
            remain -= 1
            break

print(ans)


Fixed submission:
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

inf = 10**9
dp = [-inf]*(N+1)
dp[0] = 0


for a in A:
    for j in range(d[a], N + 1):
        dp[j] = max(dp[j], dp[j - d[a]] + 1)

ans = ""
remain = dp[N]
match = N
while match > 0:
    for a in A:
        if match - d[a] < 0:
            continue
        if dp[match - d[a]] == remain - 1:
            ans += str(a)
            match -= d[a]
            remain -= 1
            break

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
if K == 0:
    print(sum(map(int, input().split())))
    exit()

D = K.bit_length()
bit = [0] * D
for a in map(int, input().split()):
    i = 0
    while a:
        if a & 1:
            bit[i] += 1
        a >>= 1
        i += 1

tight = 0
loose = 0

val = 1 << (D - 1)
for i in reversed(range(D)):
    if (K >> i) & 1:
        loose += val * max(bit[i], N - bit[i])
        loose = max(loose, tight + val * (N - bit[i]))
        tight += val * bit[i]
    else:
        tight += val * (N - bit[i])
        loose += val * max(bit[i], N - bit[i])
    val >>= 1

print(max(loose, tight))

Fixed submission:
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

one = np.zeros(40, dtype=int)
for i in range(40):
    one[i] = np.count_nonzero(a % 2)
    a >>= 1
zero = n-one

bk = bin(k)[2:].zfill(40)
bk = bk[::-1]
answer = 0
tmp = 0
for i in range(40 - 1, -1, -1):
    if bk[i] == "0":
        tmp += one[i] * (2 ** i)
    else:
        ans = tmp + one[i] * (2 ** i)
        for j in range(i - 1, -1, -1):
            ans += max(one[j], zero[j]) * (2 ** j)
        answer = max(answer, ans)
        tmp += zero[i] * (2 ** i)
else:
    answer = max(answer, tmp)

print(answer)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
DT = []
for _ in range(N):
    t, d = map(int, input().split())
    DT.append((d, t))

DT.sort(reverse=True)
score = 0
kind = defaultdict(list)
used = [0] * (N + 1)
for d, t in DT[:K]:
    score += d
    used[t] += 1
    kind[t].append(d)

cnt = len(kind)
ans = score + (cnt * cnt)

cand = []  # 交換する可能性のあるやつ, 小さいやつから削除
for key, val in kind.items():
    val.sort(reverse=True)
    while len(val) > 1:
        heapq.heappush(cand, (val.pop(), key))


for d_in, t_in in DT[K:]:
    if not kind:
        break
    if used[t_in]:
        continue

    d_out, t_out = heapq.heappop(cand)
    used[t_in] += 1
    used[t_out] -= 1
    cnt += 1
    score = score - d_out + d_in
    ans = max(ans, score + (cnt * cnt))

print(ans)

Fixed submission:
from collections import defaultdict
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
U = 10 ** 5 + 1

N, K = map(int, input().split())
DT = []
for _ in range(N):
    t, d = map(int, input().split())
    DT.append((d, t))

DT.sort(reverse=True)
score = 0
kind = defaultdict(list)
used = [0] * (U + 1)
for d, t in DT[:K]:
    score += d
    used[t] += 1
    kind[t].append(d)

cnt = len(kind)
ans = score + (cnt * cnt)

cand = []  # 交換する可能性のあるやつ, 小さいやつから削除
for key, val in kind.items():
    val.sort(reverse=True)
    while len(val) > 1:
        heapq.heappush(cand, (val.pop(), key))


for d_in, t_in in DT[K:]:
    if not cand:
        break
    if used[t_in]:
        continue

    d_out, t_out = heapq.heappop(cand)
    used[t_in] += 1
    used[t_out] -= 1
    cnt += 1
    score = score - d_out + d_in
    ans = max(ans, score + (cnt * cnt))

print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
w = list("keyence")

st = ""
i_w = 0
delete = []

for i in s:
    if i == w[i_w]:
        i_w += 1
        if not st == "":
            delete.append(st)
            st = ""
    else:
        st += i
else:
    if not st == "":
        delete.append(st)

if i_w == 7 and len(delete) <= 1:
    ans = "YES"
else:
    ans = "NO"
print(ans)


Fixed submission:
s = input()

w = "keyence"
ans = "NO"

# keyencexxxxx
if s[:7] == w:
    ans = "YES"

# xxxxkeyence
if s[-7:] == w:
    ans = "YES"

# key xxx ence
for i in range(1, 7):
    ss = w[:i]
    tt = w[-7+i:]
    if s[: len(ss)] == ss and s[-len(tt):] == tt:
        ans = "YES"
        break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,W=map(int,input().split())
w,v=[],[]
for i in range(n):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=np.zeros((n+1, W+1), dtype=np.int64)

for i in range(n):
    for j in range(W+1):
        if w[i]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j], dp[i][j-w[i]]+v[i])
#print(dp)
print(dp[n][W])

Fixed submission:
import numpy as np
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)])

dp = np.zeros(W+1, dtype=np.int64)

for w, v in wv:
    dp[w:] = np.maximum(dp[w:], dp[:W-w+1]+v)

ans = dp[W]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#coding: utf-8
N,W=map(int,input().split())
w_and_v=[list(map(int,input().split())) for i in range(N)]

dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):  #i番目の荷物チェック
    w,v=w_and_v[i]
    for j in range(1,W+1):  #残りjまで荷物を持てる
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
        
print(dp[N][W])

Fixed submission:
import numpy as np
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)])

dp = np.zeros(W+1, dtype=np.int64)

for w, v in wv:
    dp[w:] = np.maximum(dp[w:], dp[:W-w+1]+v)

ans = dp[W]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(Ns):
    for j in range(Nt):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

ans = ans[::-1]
print(ans)


Fixed submission:
# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(1, Ns + 1):
    s = S[i-1]
    for j in range(1, Nt + 1):
        t = T[j-1]
        if s == t:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += S[i-1]
        i -= 1
        j -= 1

ans = ans[::-1]
print(ans)

Fixed submission:
# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid=grid.tolist()
    
mod = 10**9+7
cost = [[0]*(W+2) for _ in range(H+2)]
seen = [[False]*(W+2) for _ in range(H+2)]

cost[1][1] = 1
seen[1][1] = True
node = deque([(1, 1)])
while node:
    x, y = node.popleft()
    c = cost[x][y]

    if grid[x+1][y] == 1:
        cost[x+1][y] += c
        cost[x+1][y] %= mod
        if not seen[x+1][y]:
            seen[x+1][y] = True
            node.append((x+1, y))

    if grid[x][y + 1] == 1:
        cost[x][y+1] += c
        cost[x][y+1] %= mod
        if not seen[x][y+1]:
            seen[x][y+1] = True
            node.append((x, y+1))


ans = cost[H][W]
print(ans)


Fixed submission:
import numpy as np
from collections import deque
H, W = map(int, input().split())
grid = np.zeros((H + 2, W + 2), dtype=int)
for i in range(H):
    grid[i+1][1:-1] = [1 if j == "." else 0 for j in input()]
grid = grid.tolist()

mod = 10**9+7
cost = [[0]*(W+2) for _ in range(H+2)]

cost[1][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        c = cost[i][j]
        if grid[i+1][j]:
            cost[i+1][j] += c
            cost[i+1][j] %= mod
        if grid[i][j+1]:
            cost[i][j+1] += c
            cost[i][j+1] %= mod

ans = cost[H][W]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N = int(input())
P = list(map(float, input().split()))

dp = defaultdict(float)
dp[(0, 0)] = 1.0

for p in P:
    newDP = defaultdict(float)
    for (X, Y), val in dp.items():
        # 表が出る
        newDP[(X + 1, Y)] += val * p
        # 裏が出る
        newDP[(X, Y + 1)] += val * (1 - p)
    dp = newDP

ans = 0.0
for x in range(N + 1):
    y = N - x
    if x > y:
        ans += dp[(x, y)]

print(ans)

Fixed submission:
import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

dp = np.zeros(N + 1, dtype=float)
dp[0] = 1 - P[0]
dp[1] = P[0]

for i in range(N - 1):
    newDP = dp * (1 - P[i + 1])
    newDP[1:] += dp[:-1] * P[i + 1]
    dp = newDP.copy()

n = (N + 1) // 2
ans = dp[n:].sum()
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_a = max(A)

dp = [0] * (K+1)

for a in A:
    dp[a] = 1

for i in range(max_a + 1, K + 1):
    for a in A:
        if dp[i - a] == 0:
            dp[i] = 1
            break
    else:
        dp[i] = 0

ans = "First" if dp[i] else "Second"
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
max_a = A[-1]

dp = [0] * (K+1)

for a in A:
    dp[a] = 1

for i in range(1, K + 1):
    bl = False
    for a in A:
        if i - a < 0:
            break
        if dp[i - a] == 0:
            bl = True
            break
    dp[i] = 1 if bl else 0


ans = "First" if dp[K] else "Second"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

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

for d in range(1, N + 1):
    for i in range(N - d + 1):
        j = i + d
        if (N-d) % 2 == 1:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
        else:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])

ans = dp[0][N]
print(ans)


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

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

for d in range(1, N + 1):
    for i in range(N - d + 1):
        j = i + d
        if (N-d) % 2 == 1:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
        else:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])

ans = dp[0][N]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
Acum = 0
mod = 10 ** 9 + 7


dp = [0]*(K+1)
dp[0] = 1

for a in A:
    Acum += a
    newDP = [0]*(K+1)
    for i in range(min(Acum, K) + 1):
        if i == 0:
            newDP[i] = 1
            continue
        dp[i] += dp[i - 1]
        newDP[i] = dp[i]
        if i > a:
            newDP[i] -= dp[i - a - 1]
        newDP[i] %= mod
    dp = newDP[::]

ans = dp[K]
print(ans)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
Acum = 0
mod = 10 ** 9 + 7


dp = [0]*(K+1)
dp[0] = 1

for a in A:
    Acum += a
    newDP = [0]*(K+1)
    for i in range(min(Acum, K) + 1):
        if i == 0:
            newDP[i] = 1
            continue
        dp[i] += dp[i - 1]
        newDP[i] = dp[i]
        if i > a:
            newDP[i] -= dp[i - a - 1]
        newDP[i] %= mod
    dp = newDP[::]

ans = dp[K]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0]+list(map(int, input().split()))

# 区間[i, j)の質量の合計はAcum[j-1] - Acum[i]
Acum = A[::]
for i in range(N):
    Acum[i + 1] += Acum[i]


cost = [[-1] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    cost[i][i + 1] = 0


def slime(i, j):
    if cost[i][j] != -1:
        return cost[i][j]

    res = 10 ** 18
    mass = Acum[j] - Acum[i]
    for x in range(i + 1, j):
        res = min(res, mass + slime(i, x) + slime(x, j))
    cost[i][j] = res
    return res


ans = slime(0, N)
print(ans)


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0]+list(map(int, input().split()))

# 区間[i, j)の質量の合計はAcum[j-1] - Acum[i]
Acum = A[::]
for i in range(N):
    Acum[i + 1] += Acum[i]


cost = [[-1] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    cost[i][i + 1] = 0


def slime(i, j):
    if cost[i][j] != -1:
        return cost[i][j]

    res = 10 ** 18
    mass = Acum[j] - Acum[i]
    for x in range(i + 1, j):
        res = min(res, mass + slime(i, x) + slime(x, j))
    cost[i][j] = res
    return res


ans = slime(0, N)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7


def mat_mul(A, B):
    # A,Bは正方行列とする
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N)) % mod
    return C


def matpow(A, n):
    B = [[0]*N for _ in range(N)]
    for i in range(N):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = mat_mul(A, B)
        A = mat_mul(A, A)
        n //= 2
    return B


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    A = matpow(A, K)
    ans = 0
    for a in A:
        ans = (ans + sum(a)) % mod
    print(ans)


Fixed submission:
mod = 10**9+7


def mat_mul(A, B):
    # A,Bは正方行列とする
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N)) % mod
    return C


def matpow(A, n):
    B = [[0]*N for _ in range(N)]
    for i in range(N):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = mat_mul(A, B)
        A = mat_mul(A, A)
        n //= 2
    return B


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    A = matpow(A, K)
    ans = 0
    for a in A:
        ans = (ans + sum(a)) % mod
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


N = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(N))

score = [0] * (1 << N)
for bit in range(1 << N):
    for i in range(N-1):
        if (bit >> i) & 1:
            for j in range(i + 1, N):
                if (bit >> j) & 1:
                    score[bit] += A[i][j]

@lru_cache(maxsize=None)
def group(bit):
    res = 0
    A = bit
    while bit:
        tmp = score[bit] + group(A & ~bit)
        res = max(res, tmp)
        bit = (bit - 1) & A
    return res


print(group((1 << N)-1))

Fixed submission:
from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


N = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(N))

score = [0] * (1 << N)
for bit in range(1 << N):
    for i in range(N-1):
        if (bit >> i) & 1:
            for j in range(i + 1, N):
                if (bit >> j) & 1:
                    score[bit] += A[i][j]


dp = [0] * (1 << N)
for bit in range(1 << N):
    sub = bit
    while True:
        dp[bit] = max(dp[bit], dp[sub] + score[bit & ~sub])
        sub = (sub - 1) & bit
        if bit == sub:
            break

print(dp[(1 << N) - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
query = tuple(map(int, input().split()))

for k in query:
    D = 0
    M = 0
    DM = 0
    res = 0
    for i, s in enumerate(S):
        if i >= k:
            if S[i - k] == "D":
                DM -= M
                D -= 1
            elif S[i - k] == "M":
                M -= 1
        if s == "D":
            D += 1
        elif s == "M":
            M += 1
            DM += D
        elif s == "C":
            res += DM
    print(res)

Fixed submission:
N = int(input())
S = input()
Q = int(input())
query = tuple(map(int, input().split()))

for k in query:
    D = 0
    M = 0
    DM = 0
    res = 0
    for i, s in enumerate(S):
        if i >= k:
            if S[i - k] == "D":
                DM -= M
                D -= 1
            elif S[i - k] == "M":
                M -= 1
        if s == "D":
            D += 1
        elif s == "M":
            M += 1
            DM += D
        elif s == "C":
            res += DM
    print(res)