Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def f(A,N,k,x):
  C=[A[(i+k)%N]^x for i in range(N)]
  return C

import numpy as np
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

M=max(A+B)
Msup=2**(int(np.log2(M)+1))

for k in range(0,N):
  for x in range(0,Msup+1):
    if f(A,N,k,x)==B:
      print(k,"",x)


Fixed submission:
K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[A[i]//2 for i in range(len(A))]

from fractions import gcd 
x=B[0]
for i in range(1,N):
  x=(x*B[i])//gcd(x,B[i])
lcm=x  
if all((lcm//b)%2==1 for b in B):
  Max=M//lcm
  if MaX%2==1:
    print((Max+1)//2)
  else:
    print((Max)//2)
else:
  print(0)


Fixed submission:
K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[A[i]//2 for i in range(len(A))]

import math
ans=B[0]
for i in range(1,N):
  ans=math.gcd(ans,B[i])
mul=B[0]//ans
for j in range(1,N):
  mul=mul*(B[j]//ans)
lcm=ans*mul

if all((lcm//b)%2==1 for b in B):
  Max=M//lcm
  if MaX%2==1:
    print((Max+1)//2)
  else:
    print((Max)//2)
else:
  print(0)


Fixed submission:
K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")

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

def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  M=len(x)
  for i in range (x):
    k=0
    for j in range(i,M):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(M-i-1)
  return result

print(abs(f(P)-f(Q)))


Fixed submission:
K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")

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

def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  M=len(x)
  for i in range (x):
    k=0
    for j in range(i,M):
      if x[i]>x[j]:
        k=k+1
      result=result+k*mul(M-i-1)
  return result

print(f(P)-f(Q))


Fixed submission:
K,X=map(int,input().split())
if K*500>=X:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=[str(input()) for i in range N]
print(S.count("ABC"))

Fixed submission:
N=int(input())
S=str(input())
print(S.count("ABC"))

Buggy python submission (verdict: Runtime Error):
N=int(input())
S=[input() for i in range (N)]
S.count("ABC")

Fixed submission:
N=int(input())
S=str(input())
print(S.count("ABC"))
Buggy python submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))

def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  M=len(x)
  for i in range (x):
    k=0
    for j in range(i,M):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(M-i-1)
  return result

print(abs(f(P)-f(Q)))


Fixed submission:
def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  N=len(x)
  for i in range (N):
    k=0
    for j in range(i,N):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(N-i-1)
  return result

N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))

print(abs(f(P)-f(Q)))

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

def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  M=len(x)
  for i in range (x):
    k=0
    for j in range(i,M):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(M-i-1)
  return result

print(f(P)-f(Q))


Fixed submission:
def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  N=len(x)
  for i in range (N):
    k=0
    for j in range(i,N):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(N-i-1)
  return result

N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))

print(abs(f(P)-f(Q)))

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

def mul(n):
  s=1
  for t in range(n):
    s=s*t
  return s

def f(x):
  result=0
  M=len(x)
  for i in range (x):
    k=0
    for j in range(i,M):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(M-i-1)
  return result

print(f(P)-f(Q))

Fixed submission:
def mul(n):
  s=1
  for t in range(1,n+1):
    s=s*t
  return s

def f(x):
  result=0
  N=len(x)
  for i in range (N):
    k=0
    for j in range(i,N):
      if x[i]>x[j]:
        k=k+1
    result=result+k*mul(N-i-1)
  return result

N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))

print(abs(f(P)-f(Q)))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N=int(input())
    A=[int(n) for n in input().split()]
    p = 1
    ov = False
    for i in range(N):
        np = p * A[i]
        if np > 10**18:
            ov = True
        if A[i] == 0:
            print(0)
            return
        p = np
    if ov:
        print(-1)
    else:
        print(np)
main()

Fixed submission:
def main():
    N=int(input())
    A=[int(n) for n in input().split()]
    p = 1
    ov = False
    for i in range(N):
        if not ov:
            np = p * A[i]
        if np > 10**18:
            ov = True
        if A[i] == 0:
            print(0)
            return
        p = np
    if ov:
        print(-1)
    else:
        print(np)
main()
Buggy python submission (verdict: Runtime Error):
a, b, c, d = map(int, input().split())
if c // b >= a // d:
    print('Yes')
else:
    print('No')

Fixed submission:
s, w = map(int, input().split())
if s > w:
    print('safe')
else:
    print('unsafe')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(int(i) for i in input().split()) 
n = N//2
cnt = 0
data = sorted(L)
data1 = data[:n]
data2 = data[n:]
for i in range(100000):
    if max(data1) < i and i <= min(data2):
        cnt += 1
print(cnt)

Fixed submission:
N = int(input())
L = list(int(i) for i in input().split()) 
n = N//2
data = sorted(L)
data1 = data[:n]
data2 = data[n:]
print(min(data2) - max(data1))
Buggy python submission (verdict: Runtime Error):
A, B, C, X  = map(int, input().split())
tmp = 0
for a in range(0,(A+1)):
    for b in range(0,(B+1)):
        for c in range(0,(C+1)):
            total = 500*a + 100*b + 50*c
            if total == X:
                tmp += 1    
print(tmp)

Fixed submission:
A = int(input())
B = int(input())
C = int(input())
X = int(input())
tmp = 0
for a in range(0,(A+1)):
    for b in range(0,(B+1)):
        for c in range(0,(C+1)):
            total = 500*a + 100*b + 50*c
            if total == X:
                tmp += 1    
print(tmp)
Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
        for z in range(0,(K+1)):
            if x + y + z == S:
                tmp += 1
print(tmp)

Fixed submission:
K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
            if 0 <= S - x - y <= K:
                tmp += 1
print(tmp)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
        for z in range(0,(K+1)):
            if x + y + z == S:
                tmp += 1
print(tmp)

Fixed submission:
K, S = map(int, input().split())
tmp = 0
for x in range(0,(K+1)):
    for y in range(0,(K+1)):
            if 0 <= S - x - y <= K:
                tmp += 1
print(tmp)
Buggy python submission (verdict: Runtime Error):
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {

	long N,M; cin >> N >> M;
	long K; cin >> K;
	
	vector<long> A(N+1,0);
	for (int i = 1; i <= N; i++) {
		int a; cin >> a;
		A[i] = A[i-1] + a;
	}

	vector<long> B(M+1,0);
	for (int i = 1; i <= M; i++) {
		int b; cin >> b;
		B[i] = B[i-1] + b;
	}

	long ans = 0;
	long best = M;
	for (int i = 1; i <= N; i++) {
		if (A[i] > K) {
			break;	
		}
		
		while (1 < best and B[best] > K - A[i]) {
			best--;		
		}
		ans = max(ans, i+best);

	}
	cout << ans << endl;



	return 0;
}


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

a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])
      
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)

main()

Fixed submission:
def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)
                exit()

main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1

main()

Fixed submission:
def main():
    k = int(input())
    a = 7
    c = 1
    b = 7
    if k == 2 or k == 5:
        print(-1)
        exit()
    while True:
        if a%k== 0:
            print(c)
            break
        else:
            b = (b*10)%k
            a = b+a
            a = a %k
            c += 1
            if c > k:
                print(-1)
                exit()

main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)

    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * pow(fact[i],MOD-2,MOD) % MOD * pow(fact[n-i],MOD-2,MOD) % MOD
        b += (-1)**(i) * nCr * fact[m-i] % MOD * pow(fact[m-n],MOD-2,MOD) % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()




Fixed submission:

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    fact_inv = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)
    fact_inv = [1] * (m+1)
    fact_inv[m] = pow(fact[m],MOD-2,MOD)
    for i in range(m):
        fact_inv[m-i-1] = fact_inv[m-i] * (m-i) % MOD
    # print(fact_inv)


    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * fact_inv[i] % MOD * fact_inv[n-i] % MOD
        b += (-1)**(i%2) * nCr * fact[m-i] % MOD * fact_inv[m-n] % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)
    # print(fact)

    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * pow(fact[i],MOD-2,MOD) * pow(fact[n-i],MOD-2,MOD) % MOD
        b += (-1)**(i) * nCr * fact[m-i] * pow(fact[m-n],MOD-2,MOD) % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()



Fixed submission:

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    fact_inv = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)
    fact_inv = [1] * (m+1)
    fact_inv[m] = pow(fact[m],MOD-2,MOD)
    for i in range(m):
        fact_inv[m-i-1] = fact_inv[m-i] * (m-i) % MOD
    # print(fact_inv)


    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * fact_inv[i] % MOD * fact_inv[n-i] % MOD
        b += (-1)**(i%2) * nCr * fact[m-i] % MOD * fact_inv[m-n] % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    dp = [True] * (max(A)+1)

    for a in A:
        c = 2
        while a*c <= max(A):
            dp[a*c] = False
            c += 1
    

    d = defaultdict(int)

    for a in A:
        d[a] += 1

    ans = 0
    for a in A:
        if dp[a] == True and d[a]==1:
            ans += 1
    print(ans)

main()

Fixed submission:
from collections import defaultdict

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    T = A[-1]+1

    dp = [True] * T

    d = defaultdict(int)

    for a in A:
        d[a] += 1
        if dp[a]:
            for j in range(2*a,T,a):
                dp[j] = False

    ans = 0
    
    for a in A:
        if d[a] == 1 and dp[a] == True:
            ans += 1

    print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 1
for a in A:
    ans *= a
    if a == 0:
        print(0)
        exit()
if ans > 10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
zero = A.count(0)
one = A.count(1)

if zero >= 1:
    print(0)
elif (N - one) > 100:
    print(-1)
else:
    ans = 1
    for a in A:
        ans *= a
    if ans > 10**18:
        print(-1)
    else:
        print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

MAX = []
e = 1
for a in A:
    if e > 0:
        MAX.append(e)
        e -= a
        e *= 2
    else:
        print(-1)
        exit()

A.reverse()
MAX.reverse()
ans = []
s = 0
for i,a in enumerate(A):
    if MAX[i] < s//2 + a:
        ans[-1] = (MAX[i] - a) * 2 + 1
        s = MAX[i]
    else:
        s += a
        s = min(MAX[i],s)
    ans.append(s)
print(sum(ans))

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

SUM = sum(A)

ans = 0
node = 1
for i,leaf in enumerate(A):
    if i == 0:
        non_leaf = 1 - leaf
        ans += 1
        if non_leaf <0:
            print(-1)
            exit()
    else:
        left,right = non_leaf,non_leaf*2
        if SUM < left or non_leaf <= 0:
            print(-1)
            exit()
        node = min(right,SUM)
        ans += node
        non_leaf = node - leaf
        SUM -= leaf
        if non_leaf < 0:
            print(-1)
            exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N = int(input())
bul = defaultdict(int)
bul2 = defaultdict(int)
for _ in range(N):
    a,b = map(int,input().split())
    bul[a/b] += 1
    bul2[-(b/a)] += 1

ALL = pow(2,N,MOD)-1

for k in bul.keys():
    if k <= 0:
        ALL -= bul2[k] * bul[k] * (N-1)
        ALL %= MOD

print(ALL)




Fixed submission:
from collections import defaultdict
import math

def main():
    MOD = 10**9+7
    N = int(input())
    zero_cnt = 0
    L = defaultdict(int)
    L2 = defaultdict(int)
    for _ in range(N):
        x,y = map(int,input().split())
        if x == 0 and y == 0:
            zero_cnt += 1
            continue
        d = math.gcd(x,y)
        x //= d
        y //= d
        if x == 0 and y == 0:
            zero_cnt += 1
        if y < 0:
            x *= -1
            y *= -1
        elif ｙ == 0 and ｘ < 0:
            x *= -1
            y *= -1
        rot90 = (x <= 0)
        if rot90:
            tmp = x
            x = y
            y = -tmp
        if rot90:
            L[(x,y)] += 1
        else:
            L2[(x,y)] += 1

    ans = 1
    keys = set(list(L.keys()) + list(L2.keys()))
    for k in keys:
        now = 1
        s = L[k]
        t = L2[k]
        now += pow(2,s,MOD) - 1
        now += pow(2,t,MOD) -1
        ans *= now
        ans %= MOD
    ans -= 1
    ans += zero_cnt
    print(ans%MOD)

main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

N ,M = map(int,input().split())
H = list(map(int,input().split()))
graph = defaultdict(list)
for _ in range(M-1):
    A, B = map(int,input().split())
    graph[A].append(H[B-1])
    graph[B].append(H[A-1])

cnt = 0
for i in range(1,N+1):
    t = H[i-1]
    a = max(graph[i])
    if t >a:
        cnt += 1
print(cnt)

Fixed submission:
from collections import defaultdict

N ,M = map(int,input().split())
H = list(map(int,input().split()))
graph = defaultdict(int)
for _ in range(M):
    A, B = map(int,input().split())
    graph[A]= max(graph[A],H[B-1])
    graph[B]= max(graph[B],H[A-1])

print(sum(H[i-1] > graph[i] for i in range(1,N+1)))
Buggy python submission (verdict: Time Limit Exceeded):
import collections
import itertools

X = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a = prime_factorize(X)
L = len(a)

for i in range(L+1):
    d = itertools.combinations(a,i)
    Y = 1
    if i != 0:
        for j in d:
            Y *= j[0]
    A = -X
    while A < X+1:
        if A ** 5 - (A-Y)**5 == X:
            print(A,A-Y)
            exit()
        else:
            A += 1

Fixed submission:
X = int(input())

for i in range(-200,200):
    for j in range(-200,200):
        if i ** 5 - j ** 5 == X:
            print(i,j)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
A, B, N = map(int,input().split())
MAX = -10**18
d = min(B,N)
for i in range(0,d+1):
    a = (A *i) //B -A * (i//B)
    MAX = max(a,MAX)
print(MAX)

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

if N >= B:
    x = B -1
else:
    x = N
MAX = 0
# for i in range(1,N+1):
#     MAX = max(MAX, (A*i)//B - A*(i//B))
# print(MAX)


ans = (A*x)//B - A*(x//B)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)

candi = []
for i in range(0,M-4):
    for j in range(i+4,M+1):
        if sum(N[i:j]) % 3==0:
            ans = N[i]
            for a in N[i+1:j]:
                ans = (ans * 10 + a)%673
            if ans == 0:
                cnt += 1
                

print(cnt)

Fixed submission:
from collections import Counter

N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)
ans = 0
mod_list = [0]
ten = 1

for n in N[::-1]:
    ans += ten*n
    mod_list.append(ans%MOD)
    ten *= 10
    ten %= MOD

SUM = 0
for k,v in Counter(mod_list).items():
    SUM += v * (v-1) /2

print(int(SUM))

Buggy python submission (verdict: Time Limit Exceeded):
N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)
for i in range(0,M):
    n = N[i]
    for j in range(i+1,M):
        n = ((n * 10) + N[j])%MOD
        if n == 0:
            cnt += 1

print(cnt)

Fixed submission:
from collections import Counter

N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)
ans = 0
mod_list = [0]
ten = 1

for n in N[::-1]:
    ans += ten*n
    mod_list.append(ans%MOD)
    ten *= 10
    ten %= MOD

SUM = 0
for k,v in Counter(mod_list).items():
    SUM += v * (v-1) /2

print(int(SUM))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split(' ')]

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split(' ')]

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

R = [v for v,i in enumerate(S) if i == 'R']
G = [v for v,i in enumerate(S) if i == 'G']
B = [v for v,i in enumerate(S) if i == 'B']
t = len(B)
c = 0
for i in R:
    for j in G:
        a = max(i,j)
        b = min(i,j)
        d = [2* b -a,2 * a - b,(a+b)/2]
        for s in d:
            if s in B:
                c -= 1
        c += t

print(c)

Fixed submission:
N = int(input())
S = input()

R = set([v for v,i in enumerate(S) if i == 'R'])
G = set([v for v,i in enumerate(S) if i == 'G'])
B = set([v for v,i in enumerate(S) if i == 'B'])
t = len(B)
c = 0
for i in R:
    for j in G:
        d = [2* i -j,2 * j - i,(i+j)/2]
        for a,s in enumerate(d):
            if s in B:
                c -= 1
        c += t

print(c)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

R = [v for v,i in enumerate(S) if i == 'R']
G = [v for v,i in enumerate(S) if i == 'G']
B = [v for v,i in enumerate(S) if i == 'B']

c = 0
for i in R:
    for j in G:
        for k in B:
            t = [i,j,k]
            t.sort()
            if not t[0] + t[2] == 2 * t[1]:
                c += 1

print(c)

Fixed submission:
N = int(input())
S = input()

R = set([v for v,i in enumerate(S) if i == 'R'])
G = set([v for v,i in enumerate(S) if i == 'G'])
B = set([v for v,i in enumerate(S) if i == 'B'])
t = len(B)
c = 0
for i in R:
    for j in G:
        d = [2* i -j,2 * j - i,(i+j)/2]
        for a,s in enumerate(d):
            if s in B:
                c -= 1
        c += t

print(c)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(i) for i in input().split(' ')]
MOD = 10 ** 9 + 7

COUNT = {}
for i in range(K,0,-1):
    whole = (K//i)**N

    c = 2
    while i * c <= K:
        whole -= COUNT[i*c]
        c += 1

    COUNT[i] = whole % MOD

SUM = 0
for k, v in COUNT.items():
    SUM += k * v
    SUM %= MOD

print(SUM)


Fixed submission:
N, K = [int(i) for i in input().split(' ')]
MOD = 10 ** 9 + 7

COUNT = {}
for i in range(K,0,-1):
    whole = pow((K//i), N, MOD)

    c = 2
    while i * c <= K:
        whole -= COUNT[i*c]
        c += 1

    COUNT[i] = whole % MOD

SUM = 0
for k, v in COUNT.items():
    SUM += k * v
    SUM %= MOD

print(SUM)