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

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

*A, = map(int, input().split())

mod = 998244353

sumT = [0]*6005
sumT[0] = 1
sumT[A[0]] = 1

for a in A[1:]:
    for j in range(3001):
        sumT[j] *= 2

    for j in range(3000, -1, -1):
        sumT[j+a] += sumT[j] // 2
        sumT[j+a] %= mod
        sumT[j] %= mod

    sumT[0] += 1
    sumT[0] %= mod

    sumT[a] += 1
    sumT[a] %= mod


print(sumT[S] % mod)


### FIXED CODE ###

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

*A, = map(int, input().split())

mod = 998244353

sumT = [0]*6005
sumT[0] = 1
sumT[A[0]] = 1

for a in A[1:]:
    for j in range(3001):
        sumT[j] *= 2

    for j in range(3000, -1, -1):
        sumT[j+a] += sumT[j] // 2
        sumT[j+a] %= mod
        sumT[j] %= mod

    sumT[0] += 1
    sumT[0] %= mod

    sumT[a] += 1
    sumT[a] %= mod


print(sumT[S] % mod)
### BUGGY CODE ###

c=int(input())
arr=[1 for i in range(c)]
arr[0]=0
for i in range(2,c+1):
    j=i
    while j<c:
        arr[j]+=1
        j+=i
print(sum(arr))
    


### FIXED CODE ###

c=int(input())
total=c-1
for i in range(2,c):
    total+=(c-1)//i
print(total)
### BUGGY CODE ###

n, m = list(map(int, input().rstrip().split(" ")))
members = [1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  tmp_a = a
  tmp_b = b
  while members[tmp_a-1] < 0:
    tmp_a = -members[tmp_a-1]
  while members[tmp_b-1] < 0:
    tmp_b = -members[tmp_b-1]
  if a != tmp_a:
    members[a-1] = -tmp_a
  if b != tmp_b:
    members[b-1] = -tmp_b
  if tmp_a != tmp_b:
    members[tmp_a-1] += members[tmp_b-1]
    members[tmp_b-1] = -tmp_a
    if members[tmp_a-1] > members[max_idx]:
      max_idx = tmp_a-1
print(members[max_idx])


### FIXED CODE ###

def root(x, root_ls):
  if root_ls[x] < 0:
    return x
  else:
    root_ls[x] = root(root_ls[x], root_ls)
    return root_ls[x]

def unite(a, b, root_ls):
  a = root(a, root_ls)
  b = root(b, root_ls)
  if a != b:
    root_ls[a] += root_ls[b]
    root_ls[b] = a
  
n, m = list(map(int, input().rstrip().split(" ")))
members = [-1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  unite(a-1, b-1, members)
print(max([-m for m in members]))
### BUGGY CODE ###

# TLE(lr&ACsが重そう)
'''
ACが出現する場所を抑えておいて、
range内に何回出てくるか探索
'''
N, Q = list(map(int, input().split()))
S = list(str(input()))
questions = [tuple(map(int, input().split())) for _ in range(Q)]
ACs = [0] * N
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        ACs[i] = 1

for q in questions:
    print(sum(ACs[q[0]-1:q[1]-1]))


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = list(str(input()))
questions = [tuple(map(int, input().split())) for _ in range(Q)]
ACs = [0] * N

for i in range(len(S)-1):
    if S[i] == 'A' and S[i + 1] == 'C':
        ACs[i + 1] = ACs[i] + 1
    else:
        ACs[i + 1] = ACs[i]

for q in questions:
    print(ACs[q[1]-1] - ACs[q[0]-1])
### BUGGY CODE ###

def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)
z = pow(2, n-1)
for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            z //= 2
            continue
        s = down - z%(one-1)
        if s < 0:
            s += one-1
    else:
        s = (up + z%(one+1))%(one+1)
    print(solve(s))
    z //= 2

### FIXED CODE ###

def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))
### BUGGY CODE ###

n, k = map(int, input().split())
#10^9+7  で割った余り
k = k %(1000000000 + 7)
#その文字より前に大きな数字
before_cnt = 0
#その文字より後に大きな数字
after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n):
  for j in range(n):
    if n_list[i] > n_list[j]:
      #print("i",i,"j",j)
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
kurikaesi = 0
for i in range(1, k+1):
  kurikaesi += i
#print("kurikaesi",kurikaesi)
#print(after_cnt, before_cnt)
print((before_cnt*(kurikaesi-k) + after_cnt*kurikaesi)%(1000000000+7))
      

### FIXED CODE ###

n, k = map(int, input().split())
#10**9+7  で割った余り
#k = k %(10**9 + 7)
#その文字iより前に大きな数字
before_cnt = 0
#その文字より後に大きな数字
after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n-1):
  for j in range(i+1, n):
    if n_list[i] > n_list[j]:
      before_cnt+=1
    elif n_list[i] < n_list[j]:
      #print("i",i,"j",j)
      after_cnt+=1
      '''
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
'''
kurikaesi = int((1 + k)*k//2)
#print("type",type(k),"kurikaesi",kurikaesi)
#print(after_cnt, before_cnt)
print(((after_cnt*(kurikaesi-k) + before_cnt*kurikaesi))%(10**9 + 7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=0
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
    kouho=kitaiti
for j in range(N-K+1):
    if j==0:
        continue
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako.pop(0)
        kouho=max(kouho,kitaiti)
#print(kouho)
print(kouho)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=0
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
    kouho=kitaiti
b=0
for j in range(N-K+1):
    if j==0:
        continue
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako[b]
        b+=1
        kouho=max(kouho,kitaiti)
#print(kouho)
print(kouho)
### BUGGY CODE ###

def p(n):
	if n%2==0:
		return False
	for i in xrange(3,int(n**0.5)+1,2):
		if n%i==0:
			return False
	else:
		return True
		
while 1:
	n=input()
	if n==0:break
	for i in xrange(n,11,-1):
		if p(i) and p(i-2) and p(i-6) and p(i-8):
			print i
			break

### FIXED CODE ###

ref = [[[10,8],[4,4]],[[10,2],[4,2]]]
r =10000001
p = [1]*r
p[0]= p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])
		
while 1:
	try:
		n = input()
		if n == 0: break
		n -= 1-n%2
		while any(not p[n-i] for i in [0,2,6,8]):
			n -= ref[p[n-2]][p[n-6]][p[n-8]]
		print n
	except:
		pass
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, os

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()
### BUGGY CODE ###

N,Q = (int(i) for i in input().split())
X = []
for i in range(N-1):
    Y = [int(n) for n in input().split()]
    X.append(Y)
X = sorted(X, key=lambda x:x[1])
Z = [] 
for i in range(N):
    Z.append(0)
    
for i in range(Q):
    Z_1,Z_2 = (int(i) for i in input().split())
    Z[Z_1-1] = Z[Z_1-1] + Z_2

#print(X)
#print(Z)


ans=[Z[0]]

for i in range(1,N):
    ans.append(Z[i])
    for n in range(len(X)):
        if X[n][1] == i+1:
            ans[i] += ans[X[n][0]-1]
            A = n+1
        else:
            for i in range(A):
                X.pop(0)
            break

#print(ans)
print(' '.join(map(str, ans)))

### FIXED CODE ###

N,Q = (int(i) for i in input().split())
X = []
for i in range(N-1):
    Y = [int(n) for n in input().split()]
    X.append(Y)
X = sorted(X, key=lambda x:x[1])
Z = []
for i in range(N):
    Z.append(0)
    
for i in range(Q):
    Z_1,Z_2 = (int(i) for i in input().split())
    Z[Z_1-1] = Z[Z_1-1] + Z_2

#print(X)
#print(Z)


ans=[Z[0]]

for i in range(1,N):
    ans.append(Z[i])
    ans[i] += ans[X[i-1][0]-1]
    
#print(ans)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

ab=[]
n,m = map(int,input().split())


for i in range(m):
    ab.append(tuple(map(int,input().split())))

abr=[]
enabled=set()
remain=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            enabled-=enabled
            break

print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

import numpy as np

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = np.full((2000,2000),-1)
dp2 = np.full((2000,2000),-1)
dp3 = np.full((2000,2000),-1)
dp4 = np.full((2000,2000),-1)





for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

dp1 = dp1+dp2+dp3+dp4

max = max(1,np.max(dp1)-3)


print(int(max))

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

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

x = 1
y = 1
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    for j in range(2, 10**18):
        if x <= a and y <= b:
            x = a
            y = b
            break
        else:
            a = ab[i][0] * j
            b = ab[i][1] * j
print(x + y)

### FIXED CODE ###

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

x = 1
y = 1
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    m = max(-(-x // a), -(-y // b))
    x = m * a
    y = m * b
print(x + y)
### BUGGY CODE ###

import math

def minus_one(n):
    return n - 1

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

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)

### FIXED CODE ###

import math

def minus_one(n):
    return n - 1

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

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)
### BUGGY CODE ###

def main():
  from collections import defaultdict
  import bisect
  n,m = map(int,input().split())
  s = list(map(int,input().split()))
  t = list(map(int,input().split()))
  mod = 10**9+7
  p = max(n,m)
  if n>m:
    t.extend((0,)*(n-m))
  else:
    s.extend((0,)*(m-n))
  dcs = defaultdict(list)
  dct = defaultdict(list)
  dp = [[1 for i in range(p+1)] for j in range(p+1)]
  for i in range(p):
    if s[i] != 0:
      dcs[s[i]].append(i)
    if t[i] != 0:
      dct[t[i]].append(i)
  def update(i,j):
    val = dp[i-1][j-1]
    x = s[i-1]
    y = t[j-1]
    if dct[x]:
      k = bisect.bisect_left(dct[x],j-1)
      if k != 0:
        val += dp[i][dct[x][k-1]+1]-dp[i-1][dct[x][k-1]+1]
    if dcs[y]:
      l = bisect.bisect_left(dcs[y],i-1)
      if l != 0:
        val += dp[dcs[y][l-1]+1][j]-dp[dcs[y][l-1]+1][j-1]
    if x == y:
      val += dp[i-1][j-1]
    dp[i][j] = val%mod

  for i in range(1,p+1):
    for j in range(1,p+1):
      update(i,j)
  print(dp[-1][-1])
main()

### FIXED CODE ###

from collections import defaultdict
import bisect
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9+7
p = max(n,m)
if n>m:
  t.extend((0,)*(n-m))
else:
  s.extend((0,)*(m-n))
dp = [[1 for i in range(p+1)] for j in range(p+1)]
for i in range(1,p+1):
  for j in range(1,p+1):
    x = s[i-1]
    y = t[j-1]
    if x == y:
      dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod
    else:
      dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%mod
print(dp[-1][-1])
### BUGGY CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] = (dp[s + a] + dp[s]) % MOD
    if a <= S:
        dp[a] = (dp[a] + (i + 1)) % MOD
    ans = (ans + dp[S]) % MOD

print(ans % MOD)

### FIXED CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
for i in range(1,n+1):
    print(A.count(i))


### FIXED CODE ###

import collections
n=int(input())
A=list(map(int,input().split()))
cli=collections.Counter(A)
for i in range(1,n+1):
    print(cli[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

N, K = MAP()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

ans = INF
# 4点組み合わせ全部試す
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        x2, y2 = XY[j]
        for k in range(N):
            x3, y3 = XY[k]
            for l in range(N):
                x4, y4 = XY[l]
                xl, xr = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
                yl, yr = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
                # 4点の内側にいくつ点があるか数える
                k = 0
                for x5, y5 in XY:
                    if xl <= x5 <= xr and yl <= y5 <= yr:
                        k += 1
                if k >= K:
                    ans = min(ans, (xr-xl) * (yr-yl))
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
・座標圧縮
・2次元累積和
"""

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

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

# 座標圧縮
zip_x, zip_y, unzip_x, unzip_y = {}, {}, {}, {}
X2 = sorted(set(X))
Y2 = sorted(set(Y))
# この後の処理のために添字は1-indexedにする
for i in range(len(X2)):
    zip_x[X2[i]] = i+1
    unzip_x[i+1] = X2[i]
for i in range(len(Y2)):
    zip_y[Y2[i]] = i+1
    unzip_y[i+1] = Y2[i]

# 圧縮した座標に点を割り当て(グリッドは累積和用に一回り大きく作る)
grid = [[0] * (len(X2)+1) for _ in range(len(Y2)+1)]
for i in range(N):
    grid[zip_y[Y[i]]][zip_x[X[i]]] += 1

# 2次元累積和
for i in range(len(Y2)+1):
    for j in range(1, len(X2)+1):
        grid[i][j] += grid[i][j-1]
for i in range(1, len(Y2)+1):
    for j in range(len(X2)+1):
        grid[i][j] += grid[i-1][j]

ans = float('inf')
for i in range(1, len(Y2)+1):
    for j in range(1, len(X2)+1):
        # 終点がK以上あれば始点を動かし始める
        if grid[i][j] >= K:
            for k in range(i):
                for l in range(j):
                    # 部分累積和を出して、点がK以上あるか確認
                    if grid[i][j] - grid[i][l] - grid[k][j] + grid[k][l] >= K:
                        # 長方形の面積を出して最小を保持
                        ans = min((unzip_x[j]-unzip_x[l+1]) * (unzip_y[i]-unzip_y[k+1]), ans)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1==0:
        return
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, q = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)
    d[b].append(a)
d2 = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    d2[p-1] += x

ans = [0] * n

def dfs(cur, pre, point):
    point += d2[cur]
    ans[cur] = point
    for e in d[cur]:
        if e != pre:
            dfs(e, cur, point)
dfs(0, -1, 0)
print(" ".join(map(str, ans)))
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(n) for n in input().split()]

    M = 10 ** 9 + 7

    combinations = [(i, j) for i in range(N-1) for j in range(i+1, N)]

    ans = 0
    for (i, j) in combinations:
        ans += A[i] * A[j] % M
    print(ans % M)


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(n) for n in input().split()]

    M = 10 ** 9 + 7

    ans = 0
    cache = sum(A) % M
    for i in range(N-1):
        cache -= A[i]
        ans += A[i] * cache % M
    print(ans % M)


main()
### BUGGY CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
count = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] + a[j] == j -i:
            count += 1
print(count)

### FIXED CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
dic ={}
res = 0
for i in range(n):
    res += dic.get(i - a[i], 0)
    dic[i + a[i]] = dic.get(i + a[i], 0) + 1

print(res)
### BUGGY CODE ###

import itertools
N=int(input())
L=list(map(int, input().split()))
S=0
C=list(itertools.combinations(L,3))
for i in range(len(C)):
    if max(C[i])*2<sum(C[i]):
        S+=1
print(S)

### FIXED CODE ###

import bisect

N=int(input())
L=sorted(list(map(int, input().split())))
S=0

for i in range(N):
    for j in range(i+1,N):
        S+=bisect.bisect_left(L,L[i]+L[j])-j-1
print(S)