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

N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    flag=0
    for j in range(len(cl))[::-1]:
        if cl[j]>a:
            cl[j]=a
            flag=1
            break
    if flag==0:
        cl.append(a)
        ans+=1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    if a>=cl[-1]:
        cl.append(a)
        ans+=1
    else:
        b=bisect.bisect_right(cl,a)
        cl[b]=a
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if (i % x == 0):
        ans += 1
print(ans)


### FIXED CODE ###

a, b, x = map(int, input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = map(int,raw_input().split())

s = []

while True:
    if not any(a):
        break
    ma = max(a)
    x = a.index(ma)
    s.append(x+1)
    b = [i for i,x in enumerate(a) if x>=1 and x == ma]
    a[b[-1]] -= 1
for i in xrange(1,n+1):
    print(s.count(i))


### FIXED CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
ans = 0

while k>0:
  #print('kは' + str(k))
  if a > 0:
    a = a-1
    ans = ans + 1
   # print('aは' + str(a))
  elif b > 0:
    b = b-1
    ans = ans + 0
    #print('bは' + str(b))
  elif c > 0:
    c = c-1
    ans = ans -1
  k = k-1
  #print(k)
print(ans)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0

if a >= k:
  ans = k
  print(ans)
elif a + b >= k:
  ans = (k-b)
  print(ans)
elif a + b + c >= k :
  ans = a + (k-a-b)*(-1)
  print(ans)
### BUGGY CODE ###

import math

n, w = map(int, input().split())
weights = []
costs = []
for i in range(n):
    a,b = map(int, input().split())
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w+1)] for i in range(n)]
for i in range(w+1):
    if(i>= weights[0]):
        dp[0][i] = costs[0]

for i in range(1, n):
    for j in range(w+1):
        if(j >= weights[i]):
            val = max(dp[i-1][j], costs[i]+dp[i-1][j-weights[i]])
            dp[i][j] = val
        else:
            dp[i][j] =max(dp[i][j], dp[i-1][j])
print(dp[-1][-1])

### FIXED CODE ###

import math

n, W = map(int, input().split())
costs, weights = [], []
sum_vals = 0
for i in range(n):
    a,b =map(int, input().split())
    sum_vals+=b
    costs.append(b)
    weights.append(a)
dp = [int(10e18)+1]*(sum_vals+1)
dp[0] = 0
for item in range(0, n):
    for value_already in range(sum_vals-costs[item], -1, -1):
        dp[value_already+costs[item]] = min(dp[value_already+costs[item]], dp[value_already]+weights[item])
ans = 0
for i in range(1, sum_vals+1):
    if(dp[i]<= W):
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*k)

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print('inf')
else:
    print(-1 * ans)

### FIXED CODE ###

N, M = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*k)

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print('inf')
else:
    print(-1 * ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
li = [list(map(int,input().split())) for _ in range(q)]

for i in range(q):
    a = s[li[i][0]-1:li[i][1]]
    print(a.count("AC"))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
li = [0 for _ in range(n+1)]

for i in range(1,n):
    li[i+1] = li[i] + s[i-1:i+1].count("AC")

for i in range(q):
    l,r = map(int,input().split())
    print(li[r]-li[l])
### BUGGY CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
#S,T = map(int, input().split())
#A = list(map(int, input().split()))
#print(N)
#print(S,T)
#print(A)
S = str(input())
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = (r*g*b)
r2 = [i for i, x in enumerate(S) if x == 'R']
g2 = [i for i, x in enumerate(S) if x == 'G']
b2 = [i for i, x in enumerate(S) if x == 'B']

for i in range (0,len(r2)):
    for j in range (0,len(g2)):
        for k in range (0,len(b2)):
            lis2 =[r2[i], g2[j], b2[k]]
            lis= sorted(lis2)
            if lis[1]-lis[0] == lis[2]-lis[1]:
                ans -=1
                #print(r2[i],g2[j],b2[k])
print(ans)


### FIXED CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
S = str(input())
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = (r*g*b)
for i in range (N-2):
    for j in range (i+1,N-1):
        k = 2*j-i
        if k < N and S[i]!=S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -=1
                #print(r2[i],g2[j],b2[k])
print(ans)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]

for i in range(N):
  if K-(Q-A.count(i+1))<=0:
    print("No")
  else:
    print("Yes")
          
    
  
  

### FIXED CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
A_point=[0]*N

for a in A:
  A_point[a-1]+=1

for aa in A_point:
  if K-(Q-aa)<=0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import sys
from collections import defaultdict


def main():
    input = sys.stdin.readline

    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1
        items_sub = [v]
        while v > 0:
            v = (v - 1) // 2
            items_sub.append(v)

        m = len(items_sub)
        dp = [0] * (l + 1)
        for bit in range(1 << (m // 2)):
            s_val = s_w = 0
            for i in range(m // 2):
                if (bit >> i) & 1:
                    s_val += items[items_sub[i]][0]
                    s_w += items[items_sub[i]][1]
            if s_w <= l:
                dp[s_w] = max(dp[s_w], s_val)
        for i in range(l):
            dp[i + 1] = max(dp[i + 1], dp[i])

        ans = 0
        for bit in range(1 << (m - m // 2)):
            s_val = s_w = 0
            for i in range(m - m // 2):
                if (bit >> i) & 1:
                    s_val += items[items_sub[m // 2 + i]][0]
                    s_w += items[items_sub[m // 2 + i]][1]
            if s_w <= l:
                ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

from operator import itemgetter

n, m = map(int, input().split())
money = 0
li = sorted([list(map(int, input().split())) for _ in range(n)])

for j in range(n):
    shop = li.pop(0)
    if m < shop[1]:
        money += m * shop[0]
        break
    money += shop[0] * shop[1]
    m -= shop[1]

print(money)



### FIXED CODE ###

n, m = map(int, input().split())
money = 0
li = []

for i in range(n):
    li.append(list(map(int, input().split())))
li.sort()

for j in range(n):
    shop = li.pop(0)
    if m < shop[1]:
        money += m * shop[0]
        break
    money += shop[0] * shop[1]
    m -= shop[1]

print(money)
### BUGGY CODE ###

from collections import deque

N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

### FIXED CODE ###

from collections import deque
import time

zuru = time.time()
N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)//2
    break
print(ans)
### BUGGY CODE ###

class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))


### FIXED CODE ###

class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))
### BUGGY CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 **18
N,*A = map(int, read().split())
ans = 1
for i in A:
  ans *= i
if ans <=INF:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 **18
N,*A = map(int, read().split())
if 0 in A:
  print(0)
  sys.exit()
ans = 1
for i in A:
  ans *= i
  if ans > INF:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
ans = set(["3","5","7"])
cnt = 0

if N > 777777753:
    print("26484")
    sys.exit()

for i in range(357,N+1,2):
    list = [i for i in str(i)]
    s = set(list)
    if s == ans:
        cnt += 1

print(cnt)


### FIXED CODE ###

N = int(input())
ans = set(["3","5","7"])
list = ["3","5","7"]
x_list = ["3","5","7"]
cnt = 0
f = 0
i = 0

while f == 0:
    for j in range(3):
        num = x_list[i] + list[j]
        if int(num) > N:
            f = 1
            break
        x_list.append(num) 
    i += 1

for i in x_list:
    ans_list = [i for i in str(i)]
    s = set(ans_list)
    if s == ans:
        cnt += 1

print(cnt)
### BUGGY CODE ###


class Result:
    def __init__(self, num, result):
        self.num = num
        self.result = result


def WelcomeTo():
    N, M = map(int, input().split())
    resultlist = []
    WAcountlist = []
    for _ in range(M):
        templist = input().split()
        resultlist.append(Result(int(templist[0]), templist[1]))
    for _ in range(0, N + 1):
        WAcountlist.append(0)

    AClist = []
    for lst in resultlist:
        if lst.num in AClist:continue
        if lst.result == 'AC':
            AClist.append(lst.num)
        else:
            WAcountlist[lst.num] += 1

    WAcount = 0
    for i in AClist:
        WAcount += WAcountlist[i]

    print('{} {}'.format(len(AClist), WAcount))


WelcomeTo()


### FIXED CODE ###


class Question:
    def __init__(self, AC, WAcount):
        self.AC = AC
        self.WAcount = WAcount


def WelcomeTo():
    N, M = map(int, input().split())
    Qlist = []
    ACcount = 0
    WAcount = 0
    for _ in range(0, N + 1):
        Qlist.append(Question('False', 0))
    for _ in range(M):
        num, judge = input().split()
        num = int(num)
        if Qlist[num].AC == 'True':continue

        if judge == 'AC':
            ACcount += 1
            WAcount += Qlist[num].WAcount
            Qlist[num].AC = 'True'
        elif judge == 'WA':
            Qlist[num].WAcount += 1

    print('{} {}'.format(ACcount, WAcount))


WelcomeTo()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

li = [[]for _ in range(N+1)]
for i in lr:
    li[i[0]].append(i[1])
for i in pq:
    cnt = 0
    for j in li[i[0]:i[1]+1]:
        for x in j:
            if(x<=i[1]):
                cnt += 1
    print(cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

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

for i in lr:
    dp[i[0]][i[1]]+=1

for j in range(N+1):
    for i in range(N-1,0,-1):
        dp[i][j] += dp[i+1][j]

for i in range(N,0,-1):
    for j in range(i,N+1):
        if(j!=i):
            dp[i][j] += dp[i][j-1]

for i in pq:
    print(dp[i[0]][i[1]])
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = input()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    N = 1
    K = 1
    S = "1"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N:
    if S[i] == "0":
      cnt = -1
      i += 1
      while i < N:
        if S[i] == "0":
          cnt -= 1
          i += 1
        else:
          break
    else:
      cnt = 1
      i += 1
      while i < N:
        if S[i] == "1":
          cnt += 1
          i += 1
        else:
          break
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  i = 0
  lenSC = len(SC) - 1
  ans = 0
  while i <= lenSC:
    if SC[i] >= 0:
      cnt = 0
      k = i + K * 2
      if k > lenSC:
        k = lenSC
      for j in range(i,k + 1):
        cnt += abs(SC[j])
      if ans < cnt:
        ans = cnt
    i += 1

  print(ans)

main()

### FIXED CODE ###

import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()
### BUGGY CODE ###

p = 1
for i in range(int(input())):
    p = p * (i+1)
print(p%((10**9)+7))

### FIXED CODE ###

p = 1
for i in range(int(input())):
    p = p * (i+1)
    p = p%((10**9)+7)
print(p)
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    s_ = list(input())
    s.append("".join(sorted(s_)))

s2 = set(s)
cnt = [0] * len(s2)
for i in s2:
    cnt.append(s.count(i))

ans = 0
for k in range(len(cnt)):
    ans += (cnt[k])*(cnt[k]-1)//2
print(ans)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for _ in range(N)]
s.sort()

cnt = 0
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        cnt +=1
        ans += cnt
    else:
        cnt = 0
print(ans)
### BUGGY CODE ###

import sys
def p(s):
  sys.stderr.write(str(s)+"\n")

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

p(N)
p(Y)

Amax=min(N,Y//10000)
Bmax=min(N,Y//5000)
Cmax=min(N,Y//1000)

p(Amax)
p(Bmax)
p(Cmax)

for a in range(Amax,-1,-1):
  B=min(Bmax,N-a)
  p("B="+str(B))
  for b in range(B,-1,-1):
    C=min(Cmax,N-a-b)
    p("a="+str(a)+", B="+str(B)+", C="+str(C))
    for c in range(C,-1,-1):
      n = a+b+c
      y = (a*10000)+(b*5000)+(c*1000)
      if n==N and y==Y:
        print(a,b,c,sep=" ")
        exit()

i=-1
print(i,i,i, sep=" ")


### FIXED CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")

N,Y=map(int, input().split())
p(N,Y)

NAmax=min(N,Y//10000)
NBmax=min(N,Y//5000)
NCmax=min(N,Y//1000)
p(NAmax, NBmax, NCmax)

NA=NAmax
for a in range(NA,-1,-1):
  NB=min(NBmax,N-a)

  for b in range(NB,-1,-1):
    c = N-a-b
    y = (a*10000)+(b*5000)+(c*1000)
    if y==Y:
      print(a,b,c,sep=" ")
      exit()
      
i=-1
print(i,i,i, sep=" ")
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
def p(val):
    print(val)

sho = 10**9 +7
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        count += ((a[i]%sho)*(a[j]%sho)) % sho
        #if count > sho:
        #   count = count%sho
p(count%sho)

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
def p(val):
    print(val)
 
sho = 10**9 +7
a1 = sum(a)**2
b1 = list(map(lambda y:y**2,a))
b2=sum(b1)
result = ((a1-b2)//2)% sho
p(result)
### BUGGY CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
lst = []
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            lst.append(koyakusu)
kotae = sum(lst)
print(kotae)

### FIXED CODE ###

import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
kotae = 0
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            kotae += koyakusu
print(kotae)
### BUGGY CODE ###

H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=L.copy()
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
a=0
for h in range(H):
    for w in range(W):
        if ans[h][w]!="#":
            a=max(a, ans[h][w])
print(a)



### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



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

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
				d[x+y]%=mod
print(ans)

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)