Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[1] = 1 
cumsum = [0 for _ in range(n+1)]
cumsum[1] = 1 

# O(NK)
for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += cumsum[ri]-cumsum[li-1]
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)


### FIXED CODE ###

#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[1] = 1 
cumsum = [0 for _ in range(n+1)]
cumsum[1] = 1 

# O(NK)
for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += (cumsum[ri]-cumsum[li-1])%mod
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)
### BUGGY CODE ###

def run():
	N, M = (int(x) for x in input().split())
	i = 2
	result = 1

	while True:
		if M % i == 0 and N * i <= M:
			result = i

		i += 1
		if i * N > M:
			break

	print(result)



if __name__ == '__main__':
	run()

### FIXED CODE ###

def run():
	N, M = (int(x) for x in input().split())
	i = 2
	result = 1

	for i in range(M // N, 0, -1):
		if M % i == 0:
			print(i)
			break



if __name__ == '__main__':
	run()
### BUGGY CODE ###

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

sum_A = [0]
for i,a in enumerate(A, 1):
    sum_A.append(sum_A[i-1] + a)
    
sum_B = [0]
for i,b in enumerate(B, 1):
    sum_B.append(sum_B[i-1] + b)
    
ans = 0
    
for i in range(N+1):
    for j in range(M, -1, -1):
        if sum_A[i] + sum_B[j] > K:
            pass
        else:
            ans = max(ans, i+j)
            break
            
print(ans)

### FIXED CODE ###

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

sum_A = [0]
for i,a in enumerate(A, 1):
    tmp = sum_A[i-1] + a
    if tmp <= K:
        sum_A.append(tmp)
        mark_A = i
    else:
        break
    
sum_B = [0]
for i,b in enumerate(B, 1):
    tmp = sum_B[i-1] + b
    if tmp <= K:
        sum_B.append(tmp)
        mark_B = i
    else:
        break
    
ans = 0
j = len(sum_B) - 1

for i,a in enumerate(sum_A):
    while sum_B[j] > K - a:
        j -= 1
        
    ans = max(ans, i+j)
    
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
count ={'M':0,'A':0,'R':0,'C':0,'H':0}
init_set = set()
cnt=0

for _ in range(n):
  temp = input()
  init = temp[0]
  if init in ('M','A','R','C','H'):
    cnt+=1
    init_set.add(init)
    count[init]+=1

ans=0
ans = len(list(itertools.combinations(range(cnt),3)))

if len(init_set)<3:
  print(0)
else:  
  for key,val in count.items():
    if val==0:
      continue
    else:
      if val==1:
        continue
      elif val==2:
        ans-= len(list(itertools.combinations(range(cnt-val),1)))
      elif val>=3:
        ans-= len(list(itertools.combinations(range(val),3)))
        ans-= len(list(itertools.combinations(range(val),2))) * (cnt-val)
  else:
    print(ans)


### FIXED CODE ###

import itertools
n = int(input())
count ={'M':0,'A':0,'R':0,'C':0,'H':0}

for _ in range(n):
  temp = input()
  init = temp[0]
  if init in ('M','A','R','C','H'):
    count[init]+=1

ans=0

for x,y,z in list(itertools.combinations(count,3)):
  ans+=count[x]*count[y]*count[z]
else:
  print(ans)
### BUGGY CODE ###

X=10**9+7
a=int(input())
x=1
for i in range(1,a+1):
    x=x*i

print(x%X)


### FIXED CODE ###

X=10**9+7

def A(c,d):
    return c*d%X

a=int(input())
x=1
for i in range(1,a+1):
    x = A(x,i)

print(x)
### BUGGY CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    total %= mod
print(total)


### FIXED CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
print(total%mod)
### BUGGY CODE ###

import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(list(range(1,N+1)))
B = A-r
ans = float('inf')
for bi in range(min(B),max(B)+1):
    ans = min(ans, sum(list(map(abs,B - bi))))
print(ans)

### FIXED CODE ###

import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
if N ==1:
    ans = 0
else:
    r = np.array(list(range(1,N+1)))
    B = np.array(sorted(A-r))
    ans = float('inf')
    for i in range(max(N//2-1,0),min(N//2+2,N)):
        c = list(map(abs,(B - B[i])))
        ans = min(ans,sum(c))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def expectation(x):
    return x * (1 + x) / (2 * x)

def solve(N: int, K: int, P: "List[int]"):
    largest = 0
    if K == 1:
        largest = expectation(max(P))
        print(largest)
        return

    for i, p in enumerate(P[:-K+1]):
        summation = 0
        for k in range(K):
            summation += expectation(P[i + k])

        if summation > largest:
            largest = summation

    print(largest)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

memory = {}

def expectation(x):
    if x in memory:
        return memory[x]
    else:
        return x * (1 + x) / (2 * x)

def solve(N: int, K: int, P: "List[int]"):
    largest = 0
    if K == 1:
        largest = expectation(max(P))
        print(largest)
        return

    for i, p in enumerate(P[:-K+1]):
        if i == 0:
            summation = 0
            for k in range(K):
                summation += expectation(P[i + k])
            if summation > largest:
                largest = summation
        else:
            summation -= expectation(P[i-1])
            summation += expectation(P[i + K - 1])
            if summation > largest:
                largest = summation

    print(largest)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

dp = [0] * (W+1)

for i in range(N):
    w, v = map(int, input().split())
    tmp = dp[:]
    for j in range(W+1):
        if j  >= w:
            dp[j] = max(tmp[j], tmp[j-w] + v)
        else:
            dp[j] = tmp[j]
    
print(dp[-1])

### FIXED CODE ###

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

w, v = [0] * N, [0] * N

for i in range(N):
	w[i], v[i] = map(int, input().split())

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

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

print(dp[N][W])
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

s=input()
t=input()
@lru_cache(None)
def dp(i,j):
  if i==0 or j==0:
    return ""
  if s[i-1]==t[j-1]:
    return dp(i-1,j-1)+s[i-1]
  else:
    return dp(i,j-1) if len(dp(i,j-1))>=len(dp(i-1,j)) else dp(i-1,j)
print(dp(len(s),len(t)))
    

### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
#print(dp)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      #print(i,res)
      if dp[i][j]==0:
        break
      continue
  break
print(res)
### BUGGY CODE ###

N=int(input())
import math
n1=int(math.sqrt(N))
for i in range(1,N+1) :
  count=0
  n1 = int(math.sqrt(i))
  for x in range(1,n1+1) :
    n2 = int(math.sqrt(i-x*x))
    for y in range(1,n2+1) :
      n3 = int(math.sqrt(i - y*y-x*x))
      for z in range(1,n3) :
        if x*x+y*y+z*z+x*y+y*z+z*x==i :
          count+=1
  print(count)


### FIXED CODE ###

N=int(input())
import math
n1=int(math.sqrt(N))

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

for x in range(1,n1) :
  for y in range(1,n1) :
    for z in range(1,n1) :
      k=x*x+y*y+z*z+x*y+y*z+z*x
      if k<=N :
        list1[k-1]+=1
for item in list1 :
  print(item)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    c=1
    for i in range(1,N):
        if P[i]<min(P[:i]):
            c+=1
    print(c)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    c=1
    min_n = P[0]
    for i in range(1,N):
        if P[i]<min_n:
            min_n=P[i]
            c+=1
    print(c)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = list(map(int, input().split()))
b = [] * M
r = []
for i in range(M):
    x, y = map(int, input().split())
    g = list(range(x, y + 1))
    b.append(g)
# print(b)
for i in range(M - 1):
    r = list(set(b[i]) & set(b[i + 1]))
    # print(r)
    b[i + 1] = r
if M >= 2:
    print(len(r))

else:
    print(len(b[0]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
l = 0
r = 10000000
for i in range(M):
    x, y = map(int, input().split())
    l = max(l, x)
    r = min(r, y)

print(r - l + 1 if l <= r else 0)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, K = MAP()
    A = LIST()

    for i in range(N-K):
        print("Yes" if reduce(mul, A[i:i+K]) < reduce(mul, A[i+1:i+K+1]) else "No")




if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, K = MAP()
    A = LIST()

    for i in range(N-K):
        print("Yes" if A[i] < A[i+K] else "No")


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]
        wa = a+b
        l_part = [ i for i in l[j+1:] if i<wa ]
        count += len(l_part)
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect.bisect_left(l,l[i]+l[j]) - j - 1
print(count)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
from heapq import heappop, heapify
input = stdin.readline
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


n, m = Is()
A = LI()
tmp = 0
for i in range(m):
    b, c = Is()
    A += [c]*b
    tmp += b
heapify(A)

for i in range(tmp):
    heappop(A)

print(sum(A))


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = LI()
BC = TIR(m)
A.sort()
BC.sort(key=itemgetter(1), reverse=True)
D = []
for b, c in BC:
    D += [c]*b
    if len(D) > n:
        break

for i in range(min(n, len(D))):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break

print(sum(A))
### BUGGY CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    a_arr = [None]
    for i in range(N):
        _ = int(_in[i+1])  # type:int
        a_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    memo = []
    now = 1
    cnt = 0
    while True:
        cnt += 1
        _ = a_arr[now]
        if _ in memo or cnt>N:
            cnt = -1
            break
        elif _ == 2:
            break
        else:
            memo.append(_)
            now = _
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    a_arr = [None]
    for i in range(N):
        _ = int(_in[i+1])  # type:int
        a_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    memo = []
    now = 1
    for i in range(N):
        _ = a_arr[now]
        if _ == 2:
            cnt = i+1
            break
        else:
            now = _
    else:
        cnt = -1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

s=input()
k=2019
ans = 0
dp=[[0 for _ in range(k)] for _ in range(len(s))]
dp[0][int(s[0])] = 1
for i in range(1,len(s)):
    t = int(s[i])
    dp[i][t] += 1
    for j in range(k):
        dp[i][((10*j)+t)%k] += dp[i-1][j]
        #dp[i][j] += dp[i-1][j]
    ans += dp[i][0]
print(ans)

### FIXED CODE ###

from collections import Counter
S=list(map(int,input()))
P=2019
N=len(S)
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n):
    for j in range(1,(n-i)//2 + 1):
        if i+2*j <= n-1:
            tem = [s[i], s[i+j], s[i+2*j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)

### FIXED CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(2, n-i+1, 2):
        if i+j <= n-1:
            tem = [s[i], s[i+j//2], s[i+j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)
### BUGGY CODE ###

from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0] * 2019
dd[0] = 1

# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    tmp = s[i:n]
    # print(tmp, int(tmp) % 2019)
    dd[int(tmp) % 2019] += 1

# print(dd)
print(sum(v*(v-1)//2 for v in dd.values()))


### FIXED CODE ###

import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019

#print(b)
for i in reversed(range(0, n)):
 #   print((b[n-i-1])*int(s[i]) % 2019)
    k += (b[n-i-1])*int(s[i]) % 2019
  #  print(k, k % 2019)
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

N = int(input())

S = input()

ans = 0

for i in range(N - 2):
    S_i = S[i]
    for j in range(i, N - 1):
        if S[j] != S_i:
            S_j = S[j]
            for k in range(j, N):
                if j - i != k - j and S[k] != S_i and S[k] != S_j:
                    ans += 1
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans=S.count('R') * S.count('G') * S.count('B')
    for i in range(N):
        for d in range(N - 1):
            j = i + d
            k = j + d
            if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
    print(ans)
main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
sum = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if i < j:
            sum += A[i-1]*A[j-1]
            sum = sum%(10**9+7)
print(sum)


### FIXED CODE ###

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

mod= 10**9+7

A = sum(a)

ans=0

for i in a:
  A -= i
  A%=mod
  ans += A*i
  ans%=mod
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())

li = []
for x in range(0, S+1):
    for y in range(0, S+1-x):
        for z in range(0, S+1-x-y):
            if x + y + z == S and x <= K and y <= K and z <= K:
                li.append([x, y, z])
print(len(li))

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if S-x-y >= 0 and S-x-y <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

#E
n=int(input())
a=tuple(map(int,input().split()))
import fractions
def lcm1(a,b):
    return a*b//fractions.gcd(a,b)

def main():
    lcm=a[0]
    b_sum=0
    
    for i in range(1,n):
        lcm=lcm1(lcm,a[i])

    num=10**9+7
    for i in range(n):
        b_sum+=(lcm//a[i])%num

    print(b_sum%num)

if __name__=='__main__':
    main()

### FIXED CODE ###

#E
n=int(input())
a=tuple(map(int,input().split()))
import fractions
lcm=a[0]
b_sum=0
for i in range(1,n):
    lcm=lcm*a[i]//fractions.gcd(lcm,a[i])

num=10**9+7
for i in range(n):
    b_sum+=(lcm//a[i])

print(b_sum%num)
### BUGGY CODE ###

n=int(input())
s=input()
m=n+5
for i in range(n):
    c=0
    w=s[:i]
    e=s[i+1:]
    for j in w:
        if j=='W':
            c+=1
    for j in e:
        if j=='E':
            c+=1
    m=min(m,c)
print(m)

### FIXED CODE ###

n=int(input())
s=input()
m=n+5
w=0
e=0
for i in range(1,n):
    if s[i]=='E':
        e+=1
m=min(m,w+e)
for i in range(1,n):
    if s[i-1]=='W':
        w+=1
    if s[i]=='E':
        e-=1
    m=min(m,w+e)
print(m)