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

from itertools import combinations
s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
        elif s[i-1] != t[j-1]:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
k = dp[n][m]
p = list(combinations(range(n),k))
if k == 0:
    print()
    exit()
for i in p:
    cou = 0
    for j in range(m):
        if t[j] == s[i[cou]]:
            cou += 1
        if cou == k:
            for l in i:
                print(s[l],end="")
            print()
            exit()

### FIXED CODE ###

from itertools import combinations
s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
        elif s[i-1] != t[j-1]:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = n
j = m
ans = ""

while i > 0 and j > 0:

    if s[i-1] == t[j-1]:
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
print(ans)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
res = 0
for i in range(1,N+1):
    res_bar = math.floor((A*i)/B)-A*math.floor(i/B)
    if res_bar >= res:
        res = res_bar
    else:
        break
print(res)


### FIXED CODE ###

import math
 
a, b, n = map(int, input().split())
ans = 0
tmp = 0
 
if n > b - 1:
    n = b-1
 
ans = math.floor(a*n/b) - a*math.floor(n/b)
 
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [-1] * N
dp[0] = 0
for i_from in range(N - 1):
    for j_to in range(1, min(K + 1, N - i_from)):
        if dp[i_from + j_to] == -1:
            dp[i_from + j_to] = dp[i_from] + abs(h[i_from + j_to] - h[i_from])
        else:
            dp[i_from + j_to] = min(
                dp[i_from + j_to], dp[i_from] + abs(h[i_from + j_to] - h[i_from])
            )
print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [-1] * N
dp[0] = 0
for i_from in range(N - 1):
    for j_to in range(1, min(K + 1, N - i_from)):
        if dp[i_from + j_to] == -1:
            dp[i_from + j_to] = dp[i_from] + abs(h[i_from + j_to] - h[i_from])
        else:
            dp[i_from + j_to] = min(
                dp[i_from + j_to], dp[i_from] + abs(h[i_from + j_to] - h[i_from])
            )
print(dp[-1])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value

  if len(l[node-1])==0:
    return 0

  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

for _ in range(q):
  a,b=LI()
  update(a,b)

print(' '.join([str(x) for x in vl]))



### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]
level=[-1]*nmax

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    if level[e]==-1:
      level[e]=level[s]+1
    if level[e]>level[s]:
      l[e]+=l[s]
      dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  level[0]=0
  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

# main()
print(main())
### BUGGY CODE ###

inf = float("INF")
a,b,q = map(int, input().split())
s = [-inf, -inf]+[int(input()) for _ in range(a)]+[inf]
t = [-inf, -inf]+[int(input()) for _ in range(b)]+[inf]

from bisect import bisect_left
from collections import defaultdict

dp = defaultdict(lambda: None)

def f(s,t,x,ss,i):
  if dp[(ss,i)] != None: return abs(x - s[ss]) + dp[(ss,i)]
  tr = bisect_left(t, s[ss])
  tl = tr - 1
  dp[(ss,i)] = min(abs(s[ss] - t[tl]), abs(s[ss] - t[tr]))
  return abs(x - s[ss]) + dp[(ss,i)]


for _ in range(q):
  ans = inf
  x = int(input())
  sr = bisect_left(s, x)
  ans = min(ans, f(s,t,x,sr,0))
  ans = min(ans, f(s,t,x,sr - 1,0))
  tr = bisect_left(t, x)
  ans = min(ans, f(t,s,x,tr,1))
  ans = min(ans, f(t,s,x,tr - 1,1))
  print(ans)
  


### FIXED CODE ###

#A

"""
s = input().split("/")
if int(s[1]) <= 4:
    print("Heisei")
else:
    print("TBD")
"""
#B
"""
n = int(input())
ans = 0
for i in range(n):
    a = input().split()
    if a[1] == "JPY":
        ans += int(a[0])
    else:
        ans +=  float(a[0]) * 380000
print(ans)
"""

#C
"""
n, a, b, c = map(int, input().split())
abc = [a,b,c]
x = [int(input()) for i in range(n)]
x.sort()
ans = []
flg = 0
for i in x:
    if i in abc:
        ans.append(i)
        flg = 1
if flg:
    for i in ans:
        abc.remove(i)
        x.remove(i)

"""
#D

a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
s.sort()
t.sort()

import bisect


for i in range(q):
    x = int(input())
    s_l = bisect.bisect_left(s, x) - 1
    t_l = bisect.bisect_left(t, x) - 1
    s_r = s_l + 1
    t_r = t_l + 1
    if s_l == -1:
        s_l = 0
    if t_l == -1:
        t_l = 0
    if s_l == a :
        s_l = a - 1
        s_r = a - 1
    if s_r == a:
        s_r = a - 1
    if t_l == b:
        t_l = b - 1
        t_r = b - 1
    if t_r == b:
        t_r = b - 1
    ans = min(abs(t[t_l] - s[s_r]) + min(abs(t[t_l] - x), abs(s[s_r] - x)),
    abs(s[s_l] - t[t_r]) + min(abs(s[s_l] - x), abs(t[t_r] - x)),
    abs(s[s_l] - t[t_l]) + min(abs(s[s_l] - x), abs(t[t_l] - x)),
    abs(s[s_r] - t[t_r]) + min(abs(s[s_r] - x), abs(t[t_r] - x)),
    )
    
    print(ans)
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(N-i-1):
        if A[i] == A[i+j+1]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()

for i in range(N-1):
    if A[i] == A[i+1]:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

import math
import numpy

n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    a1=numpy.cumsum(a1)
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))


### FIXED CODE ###

import math
n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    for k in range(1,n):
        a1[k]=a1[k-1]+a1[k]
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))
### BUGGY CODE ###

M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a];e[i]+=e[i-a];i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print((z+~s%2*e[s//2]*3)%M)

### FIXED CODE ###

M,z,s=998244353,1,0
N,*A=map(int,open(0))
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 i=s;s+=a;z*=3
 while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
from itertools import accumulate



N, K = MI()
A = LMI()

for _ in range(K):
    accum = [0] * (N + 1)
    for i, a in enumerate(A):
        l, r = max(0, i - a), min(N - 1, i + a)
        accum[l] += 1
        accum[r + 1] -= 1
    accum = list(accumulate(accum))
    if accum[0] == accum[-1] == N:
        break
    A = accum[:-1]
print(*A)



### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
from itertools import accumulate


N, K = MI()
A = LMI()

for _ in range(min(50, K)):
    accum = [0] * (N + 1)
    for i, a in enumerate(A):
        l, r = max(0, i - a), min(N - 1, i + a)
        accum[l] += 1
        accum[r + 1] -= 1
    A = list(accumulate(accum))[:-1]
print(*A)
### BUGGY CODE ###

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=lambda x: x[0])
List_S = []
 
result = 0
p = 0
 
for i in range(1,M+1):
    for j in range(p,N):
        if List[j][0] <= i:
            List_S.append(List[j][1])
            p += 1
        else:
            break
    if len(List_S) != 0:
        List_S.sort(reverse = True)
        result += List_S[0]
        del List_S[0]
 
print(result)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)
### BUGGY CODE ###

from itertools import product

N = int(input())
S = input()

cnt = 0
for i, j, k in product("0123456789", repeat=3):
    T = [i, j, k]
    cur = 0
    for s in S:
        if s == T[cur]:
            cur += 1
            if cur == 3:
                cnt += 1
                break

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

L, R = [0] * 10, [0] * 10

L[int(S[0])] += 1
for s in S[2:]:
    R[int(s)] += 1

memo = set()
for i, s in enumerate(S[1:-1], 1):
    for l, v in enumerate(L):
        if v <= 0:
            continue
        for r, v in enumerate(R):
            if v <= 0:
                continue
            memo.add(str(l) + s + str(r))
    L[int(s)] += 1
    R[int(S[i + 1])] -= 1

print(len(memo))
### BUGGY CODE ###

N,A,B = map(int,input().split())
b = ''
while True:
    for i in range(A):
        if len(b) == N:
            print(b.count('b'))
            exit()
        b += 'b'
    for i in range(B):
        if len(b) == N:
            print(b.count('b'))
            exit()
        b += 'r'

### FIXED CODE ###

N,A,B = map(int,input().split())
cnt = N % (A+B)
if cnt == 0:
    print(N // (A+B) * A)
    exit()
else:
    if cnt - A >= 0:
        print(N // (A+B) * A + A)
        exit()
    else:
        print(N // (A+B) * A + cnt)
        exit()
### BUGGY CODE ###


def resolve():
    import sys
    import string
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    n, k, q = [int(x) for x in input().rstrip().split(" ")]

    scores = [k for _ in range(n)]

    for i in range(q):
        a = int(input().rstrip())
        scores = [score - 1 if i != a-1 else score for i, score in enumerate(scores)]

    for score in scores:
        if score <= 0:
            print("No")
        else:
            print("Yes")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    import sys
    import string
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    n, k, q = [int(x) for x in input().rstrip().split(" ")]

    scores = [k - q for _ in range(n)]

    for i in range(q):
        a = int(input().rstrip())
        scores[a-1] += 1


    for score in scores:
        if score <= 0:
            print("No")
        else:
            print("Yes")

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

n = int(input())
ans = 1
an = list(map(int,input().split()))
for i in range(n):
    ans = ans * an[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1
an = list(map(int,input().split()))
for i in an:
    if i == 0:
        ans = 0
if ans != 0:
    for i in range(n):
        ans = ans * an[i]
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


def main():
    N = int(input())
    A = list(map(int,input().split()))

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


def main():
    N = int(input())
    A = list(map(int,input().split()))

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()
### BUGGY CODE ###

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

    ans = 0
    import collections
    cnt = collections.Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for i, aa in enumerate(set_a):
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

N = int(input())
S = input()
out = 0
ls = []
RGB = ['R','G','B']
for i in RGB:
    ls.append([j for j, x in enumerate(S) if x == i])


# flg = [[[0 for i in range(N)] for j in range(N)] for k in range(N)]
for i in ls[0]:
    for j in ls[1]:
        for k in ls[2]:
            tmp = [i,j,k]
            tmp.sort()
            [l,m,n] = tmp
            if m-l != n-m:
                out += 1

print(out)


### FIXED CODE ###

N = int(input())
S = input()
r,g,b = S.count('R'),S.count('G'),S.count('B')
#rgbでr,g,bがすべて異なる組み合わせ数
total = r*g*b
# そこからj-i=k-jの組み合わせを引く
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k = 2*j-i
        if k >= N: break;
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            total-=1
# flg = [[[0 for i in range(N)] for j in range(N)] for k in range(N)]

print(total)
### BUGGY CODE ###

def resolve():
    (N, Q) = list(map(int, input().split(" ")))
    S = input()
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]

    for (l, r) in LRs:
        print(S[l-1:r].count("AC"))

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (N, Q) = list(map(int, input().split(" ")))
    S = input()
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]
    mem = [0] * N
    for i in range(N-1):
        if S[i] == "A" and S[i+1] == "C":
            mem[i+1] = mem[i] + 1
        else:
            mem[i+1] = mem[i]

    for (l, r) in LRs:
        print(mem[r-1]-mem[l-1])

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

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  elif seen[y][x]<=p:
    continue
  else:
    seen[y][x]=p
  ans=max(ans,p)
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline


def DFS(num,parent,point):
    D[num]=point+Q[num]
    for i in M[num]:
        if i!=parent:
            DFS(i,num,D[num])


n,q=map(int,input().split())

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

Q=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    Q[p-1] +=x

D=[0]*n
DFS(0,-1,0)
print(*D)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)
### BUGGY CODE ###

N = int(input())
nums = list(map(int,input().split()))

calcs = []
for i in range(N):
    a = nums[i]
    for j in range(i+1, N):
        calcs.append(a * nums[j])

print(sum(calcs) % (1000000000+7))

### FIXED CODE ###

N = int(input())
nums = list(map(int,input().split()))

total = 0
sums = []
tmp = 0

for i in range(1, N):
    tmp += nums[N-i]
    sums.append(tmp)

for i in range(N-1):
    a = nums[i]
    b = sums[N-(i+2)]
    total += a*sums[N-(i+2)]

print(total % (1000000000+7))
### BUGGY CODE ###

#input
N = int(input())
A = list(map(int, input().split()))

#output
from collections import Counter
l = Counter(A)
l = l.most_common()

maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A)
    l = l.most_common()
    while l[K][1] > 0:
        for i in range(K+1):
            l[i] = (l[i][0], l[i][1]-1)
        l.sort(key = lambda x:x[1], reverse = True)
        maximum_operation[K] += 1

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())
A = list(map(int, input().split()))

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

n, k = map(int, input().split())
while n ** 2 >= (n - k) ** 2:
    n -= k
print(n if n >= 0 else n * (-1))

### FIXED CODE ###

n, k = map(int, input().split())
x = n % k
while x ** 2 >= (x - k) ** 2:
    x -= k
print(x if x >= 0 else x * (-1))
### BUGGY CODE ###

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

dp = [0]*(10**6)
count = [0]*(10**6)
for i in a:
  count[i-1] += 1
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
dp = [0]*(10**6)
count = [0]*(10**6)

for i in a:
  count[i-1] += 1
 
b = list(set(a))
for i in b:
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)
### BUGGY CODE ###

import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

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

    for i in range(1, N+1):
        xi = X[i-1]
        for j in range(S+1):
            # xi を U に加えない場合
            dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない

            # xi を U に加える場合
            if j+xi > S: continue
            dp[i][j+xi] += dp[i-1][j] % MOD

    print(dp[N][S] % MOD)

main()

### FIXED CODE ###

import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    # dp = np.zeros((N+1)*(S+1), dtype=np.int).reshape((N+1),(S+1))
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()