Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def answer(s):
    YES = 'YES'
    NO = 'NO'
    dic = collections.Counter(s)
    vals = sorted([v for k,v in dic.items()], reverse=True)
    if len(vals) == 1: return YES
    elif len(vals) == 2:
        if vals[0] == 1 and vals[1] == 1: return YES
        else: return NO
    
    _max = vals[0]
    _sum = sum(vals[1:])
    if (_max-1)*2 <= _sum:
        if vals[1]-vals[2] > 1: return NO
        else: return YES
    return NO
s = input()
print(answer(s))

Fixed submission:
import collections

def answer(s):
    YES = 'YES'
    NO = 'NO'
    dic = collections.Counter(s)
    vals = sorted([v for k,v in dic.items()], reverse=True)
    if len(vals) == 1:
        if vals[0] == 1: return YES
        else: return NO
    elif len(vals) == 2:
        if vals[0] == 1 and vals[1] == 1: return YES
        else: return NO
    
    _max = vals[0]
    _sum = sum(vals[1:])
    if (_max-1)*2 <= _sum:
        if vals[1]-vals[2] > 1: return NO
        else: return YES
    return NO

s = input()
print(answer(s))

Buggy python submission (verdict: Runtime Error):
import collections

def answer(s):
    YES = 'YES'
    NO = 'NO'
    dic = collections.Counter(s)
    vals = sorted([v for k,v in dic.items()])
    _max = vals[0]
    print(_max
    if _max < 2:
        return YES
    if len(keys) == 2:
        return NO
    if (_max-1)*2 > sum(vals[1:]):
        return YES
    if (_max-1)*2 == sum(vals[1:]):
        if _max == vals[1]:
            return NO
        return YES
s = input()
print(answer(s))

Fixed submission:
import collections

def answer(s):
    YES = 'YES'
    NO = 'NO'
    dic = collections.Counter(s)
    vals = sorted([v for k,v in dic.items()], reverse=True)
    if len(vals) == 1:
        if vals[0] == 1: return YES
        else: return NO
    elif len(vals) == 2:
        if vals[0] == 1 and vals[1] == 1: return YES
        else: return NO
    
    _max = vals[0]
    _sum = sum(vals[1:])
    if (_max-1)*2 <= _sum:
        if vals[1]-vals[2] > 1: return NO
        else: return YES
    return NO

s = input()
print(answer(s))
Buggy python submission (verdict: Runtime Error):
Alice = 'A'
Bob = 'B'
Charlie = 'C'

def answer(Sa, Sb, Sc):
    currentUser = Alice
    ai, bi, ci = (0, 0, 0)
    while(True):
        if currentUser == Alice:
            if ai == len(Sa):
                return Alice
            if Sa[ai] == 'b':
                currentUser = Bob
            if Sa[ai] == 'c':
                currentUser = Charlie
            ai += 1
            continue
        if currentUser == Bob:
            if bi == len(Sb):
                return Bob
            if Sa[bi] == 'a':
                currentUser = Alice
            if Sa[bi] == 'c':
                currentUser = Charlie
            bi += 1
            continue
        if currentUser == Charlie:
            if ci == len(Sc):
                return Charlie
            if Sa[ci] == 'a':
                currentUser = Alice
            if Sa[ci] == 'b':
                currentUser = Bob
            ci += 1
            continue
            
Sa = input()
Sb = input()
Sc = input()
print(answer(Sa, Sb, Sc))

Fixed submission:
Alice = 'A'
Bob = 'B'
Charlie = 'C'

def answer(Sa, Sb, Sc):
    currentUser = Alice
    ai, bi, ci = (0, 0, 0)
    while(True):
        if currentUser == Alice:
            if ai == len(Sa):
                return Alice
            if Sa[ai] == 'b':
                currentUser = Bob
            if Sa[ai] == 'c':
                currentUser = Charlie
            ai += 1
            continue
        if currentUser == Bob:
            if bi == len(Sb):
                return Bob
            if Sb[bi] == 'a':
                currentUser = Alice
            if Sb[bi] == 'c':
                currentUser = Charlie
            bi += 1
            continue
        if currentUser == Charlie:
            if ci == len(Sc):
                return Charlie
            if Sc[ci] == 'a':
                currentUser = Alice
            if Sc[ci] == 'b':
                currentUser = Bob
            ci += 1
            continue
            
Sa = input()
Sb = input()
Sc = input()
print(answer(Sa, Sb, Sc))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
c = 0
for i in range(n-1):
  for j in range(i+1, n):
    k = j*2-i
    if k >= n:
        continue
    if len(set([s[i], s[j], s[k]]))==3:
      c += 1
print(r*g*b-c)


Fixed submission:
N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
c = 0
for i in range(N-2):
  for j in range(i+1,(i+N+1)//2):
    k = j*2-i
    if len(set([S[i], S[j], S[k]]))==3:
      c += 1
print(r*g*b-c)
Buggy python submission (verdict: Runtime Error):
M = 998244353

n = int(input())
d = list(map(int, input().split()))
idx = [0]*n
ans = 1
for i in range(n):
    idx[d[i]] += 1

if not idx[0] == 1:
    print(0)
else:
    if n == 1:
        print(1)
        break
    for i in range(1,n):
        if idx[i-1] == 0:
            if not idx[i] == 0:
                print(0)
                break
        else:
            ans *= (idx[i-1]**idx[i]%M)
    else:
        print(ans%M)


Fixed submission:
import sys
M = 998244353

n = int(input())
d = list(map(int, input().split()))
idx = [0]*n
ans = 1
for i in range(n):
    idx[d[i]] += 1

if not d[0] == 0 or not idx[0] == 1:
    print(0)
else:
    for i in range(1,n):
        if idx[i-1] == 0:
            if not idx[i] == 0:
                print(0)
                sys.exit()
        else:
            ans *= idx[i-1]**idx[i]%M
    else:
        print(ans%M)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i]+l[j] > l[k]:
                ans += 1
print(ans)


Fixed submission:
import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        idx = bisect.bisect_right(l, l[i]+l[j]-1, j+1)
        ans+=idx-(j+1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())
idx = 2
ans = 1
prime = []

while idx <= a and idx <= b:
    for num in prime:
        if idx%num == 0:
            break
    else:
        prime += [idx]
        if a%idx == 0 and b%idx == 0:
            ans += 1
            a //= idx
            b //= idx
    idx += 1
print(ans)


Fixed submission:
import math
a, b = map(int, input().split())
ans = {1}

def calc_gcd(x, y):
    if y == 0: return x
    return calc_gcd(y, x%y)

def factrize(z):
    i = 2
    set = {1}
    while i*i <= z:
        while z%i==0:
            z//=i
            set.add(i)
        i+=1
    if z > 1:
        set.add(z)
    return set

gcd = calc_gcd(a, b)
print(len(factrize(gcd)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ans = 0

for i in range(1, n):
    ans += i

print(ans)


Fixed submission:
n = int(input()) - 1
print(n*(n+1)//2)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ans = 0

for i in range(1, n):
    ans += i

print(ans)


Fixed submission:
n = int(input()) - 1
print(n*(n+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
used = []*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    used.append(k[0])
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i in used:
            q.append((i, k[0]))

print(*count[1:])


Fixed submission:
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, q = map(int, input().split())
counter = [0]*n
edges = {}

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[b] = a

for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

for i in range(1, n):
    counter[i] += counter[edges[i+1]-1]

print(*counter)

Fixed submission:
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
counter = [0]*n
edges = {}

def have(p, add_lst):
    if p not in edges.keys():
        return
    for i in edges[p]:
        add_lst += [i]
        have(i, add_lst)


for i in range(n-1):
    a, b = map(int, input().split())
    if a in edges.keys():
        edges[a] += [b]
    else:
        edges[a] = [b]

for i in range(q):
    p, x = map(int, input().split())
    add_lst = [p]
    have(p, add_lst)
    for j in add_lst:
        counter[j-1] += x

for i in range(n):
    print(counter[i], end=" ")


Fixed submission:
from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

M=10**9+7
r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
d=[1]+[0]*12
for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
print(d[5])


Fixed submission:
def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

s = [int(x) if x != "?" else -1 for x in input().strip()]
n = len(s)
m = 10**9+7
dp = [0] * 26
mul = 1

if s[-1] == -1:
    for i in range(10):
        dp[i] = 1
else:
    dp[s[-1]] = 1

for i in range(2, n + 1):
    mul *= 10

    if s[-i] == -1:
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    dp[a + 13] += dp[k]%m
    else:
        rem = (s[-i] * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                dp[a + 13] += dp[k]%m
    dp[:13] = dp[13:26]
    dp[13:26] = [0]*13
print(dp[5]%m)

Fixed submission:
def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys, copy
input = sys.stdin.readline

s = input().strip()
n = len(s)
mod = 10**9+7
dp = [0] * 13
mul = 1

if s[-1] == "?":
    for i in range(10):
        dp[i] = 1
else:
    dp[int(s[-1])] = 1

for i in range(2, n + 1):
    next_dp = [0]*13
    mul *= 10

    if s[-i] == "?":
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    next_dp[a] += dp[k]
    else:
        rem = (int(s[-i]) * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                next_dp[a] += dp[k]
    dp = copy.deepcopy(next_dp)
print(int(dp[5] % mod))

Fixed submission:
def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()
Buggy python submission (verdict: Runtime Error):
import sys
l, r = map(int, input().split())
m = 2019

if r - l + 1 >= 2019 or l == 0:
    print(0)
else:
    min = (l%m * (l+1)%m)%m
    for i in range(l, r):
        if i%m == 0:
            print(0)
            sys.exit()
        for j in range(i+1, r+1):
            else:
                if min > (i%m * j%m)%m:
                    min = (i%m * j%m)%m
print(min)


Fixed submission:
import sys
l, r = map(int, input().split())
m = 2019
min = 2019

if r - l >= 2019:
    print(0)
else:
    l, r = l%m, r%m
    for i in range(l, r):
        for j in range(i+1, r+1):
            if min > (i * j)%m:
                min = (i * j)%m
    print(min)
Buggy python submission (verdict: Time Limit Exceeded):
import collections, queue, sys
n, k =  map(int, input().split())
m = 10**9+7
edges = collections.defaultdict(list)
q = []
ans = 1

for i in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

j = 1
for i in edges[1]:
    q.append((i, 1))
    if k - j <= 0:
        print(0)
        sys.exit()
    ans = ans%m * (k - j)%m
    j+=1

while q:
    j = 2
    node = q[0][0]
    prenode = q[0][1]
    q.pop(0)
    for i in edges[node]:
        if not i == prenode:
            q.append((i, node))
            if k - j <= 0:
                print(0)
                sys.exit()
            ans = ans%m * (k - j)%m
            j+=1
print((ans*k)%m)

Fixed submission:
import collections, queue, sys
n, k =  map(int, input().split())
m = 10**9+7
edges = collections.defaultdict(list)
q = queue.Queue()
preq = queue.Queue()
ans = 1

for i in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

j = 1
for i in edges[1]:
    q.put(i)
    preq.put(1)
    if k - j <= 0:
        print(0)
        sys.exit()
    ans = ans%m * (k - j)%m
    j+=1

while not q.empty():
    j = 2
    node = q.get()
    prenode = preq.get()
    for i in edges[node]:
        if not i == prenode:
            q.put(i)
            preq.put(node)
            if k - j <= 0:
                print(0)
                sys.exit()
            ans = ans%m * (k - j)%m
            j+=1
print((ans*k)%m)
Buggy python submission (verdict: Runtime Error):
import sys

n = int(input())
d = list(map(int, input().split()))
dic = {}
val = 0

for i in range(n):
    if d[i] in dic.keys():
        dic[d[i]] += 1
    else:
        dic[d[i]] = 1

dic = sorted(dic.items())

for i in range(len(dic) - 1):
    val += dic[i][1]
    if val == n//2:
        ans = (dic[i][0] + 1, dic[i+1][0])
        break
    elif i == len(dic) - 2:
        print(0)
        sys.exit()

print(ans[1] - ans[0] + 1)


Fixed submission:
import sys

n = int(input())
d = list(map(int, input().split()))
dic = {}
val = 0

for i in range(n):
    if d[i] in dic.keys():
        dic[d[i]] += 1
    else:
        dic[d[i]] = 1

dic = sorted(dic.items())

if len(dic) == 1:
    print(0)
    sys.exit() 

for i in range(len(dic) - 1):
    val += dic[i][1]
    if val == n//2:
        ans = (dic[i][0], dic[i+1][0])
        print(ans[1] - ans[0])
        break
    elif val > n//2:
        print(0)
        break

Buggy python submission (verdict: Runtime Error):
n = int(input())
d = list(map(int, input().split()))
dic = {}
val = 0

for i in range(n):
    if d[i] in dic.keys():
        dic[d[i]] += 1
    else:
        dic[d[i]] = 1

dic = sorted(dic.items())

for i in range(len(dic) - 1):
    val += dic[i][1]
    if val == n//2:
        ans = (dic[i][0] + 1, dic[i+1][0])
        break
    elif i == len(dic) - 2:
        ans = (1, 0)
        break

print(ans[1] - ans[0] + 1)


Fixed submission:
import sys

n = int(input())
d = list(map(int, input().split()))
dic = {}
val = 0

for i in range(n):
    if d[i] in dic.keys():
        dic[d[i]] += 1
    else:
        dic[d[i]] = 1

dic = sorted(dic.items())

if len(dic) == 1:
    print(0)
    sys.exit() 

for i in range(len(dic) - 1):
    val += dic[i][1]
    if val == n//2:
        ans = (dic[i][0], dic[i+1][0])
        print(ans[1] - ans[0])
        break
    elif val > n//2:
        print(0)
        break
Buggy python submission (verdict: Runtime Error):
from math import factorial

n, k = map(int, input().split())
red = n - k
m = 10**9+7

def com_cal(p, q):
    return factorial(p) // (factorial(p - q) * factorial(q))

for i in range(1, k+1):
    com = com_cal(red + 1, i)
    div_num = com_cal(k - 1, i - 1)
    print((com * div_num)%m)


Fixed submission:
from math import factorial

n, k = map(int, input().split())
red = n - k
m = 10**9+7

def com_cal(p, q):
    return factorial(p) // (factorial(p - q) * factorial(q))

for i in range(1, k+1):
    if red+1 < i:
        print(0)
        continue
    com = com_cal(red + 1, i)
    div_num = com_cal(k - 1, i - 1)
    print((com * div_num)%m)
Buggy python submission (verdict: Runtime Error):
from math import gcd
a, b, c, d = map(int, input().split())
mc = b // c - (a-1) // c
md = b // d - (a-1) // d
mcd = b // (c*d//gcd(c, d)) - (a-1) // (c*d//gcd(c, d))

print(int((b - a + 1) - mc - md + mcd))

Fixed submission:
a, b, c, d = map(int, input().split())

def gcd(x, y):
	while y:
		x, y = y, x % y
	return x

mc = b // c - (a-1) // c
md = b // d - (a-1) // d
mcd = b // (c*d//gcd(c, d)) - (a-1) // (c*d//gcd(c, d))

print(int((b - a + 1) - mc - md + mcd))
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "#": continue
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "#": break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "#": continue
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "#": break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)


Fixed submission:
h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "#": continue
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "#": break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "#": continue
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "#": break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))

    ans = 0
    for i in range(60):
        one,zero = 0,0
        for j in range(n):
            if ((1 << i) & a[j]) == (1 << i):
                one +=1
            else:
                zero += 1
        ans += (1 << i) * one * zero
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))

    ans = 0
    for i in range(60):
        one,zero = 0,0
        for j in range(n):
            if ((1 << i) & a[j]) == (1 << i):
                one +=1
            else:
                zero += 1
        ans += (1 << i) * one * zero
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)




Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
e = [ [ ] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x

ansl = [0 for i in range(N)]

def dfs(x,c):
    c += d[x]
    ansl[x] = c
    for v in e[x]:
        dfs(v,c)

dfs(0,0)
print(" ".join(map(str,ansl)))


Fixed submission:
import sys
sys.setrecursionlimit(10000000)

def main():
    N,Q = map(int,sys.stdin.readline().split())
    e = [ [ ] for i in range(N)]
    for i in range(N-1):
        a,b = map(int,sys.stdin.readline().split())
        e[a-1].append(b-1)

    from collections import defaultdict
    d = defaultdict(int)
    for i in range(Q):
        p,x = map(int,sys.stdin.readline().split())
        d[p-1] += x

    ansl = [0 for i in range(N)]

    def dfs(x,c):
        c += d[x]
        ansl[x] = c
        for v in e[x]:
            dfs(v,c)

    dfs(0,0)
    print(" ".join(map(str,ansl)))
if __name__ == '__main__':
    main()