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

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)


#"""
#h=10**4
#n=10**3
#ma=[[i,i+1] for i in range(n)]

#ma=sorted(ma,key=lambda x:x[1])
#ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
for i in range(n):
    dp[i][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(1,h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print(dp[-1][-1])
        


### FIXED CODE ###

import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

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

def main(a):
  if 0 in a:
    ans = 0
  else:
    ans = 1
    for item in a:
      ans *= item
      if ans > 1000000000000000000:
        ans = -1
  return ans

ans = main(a)
print(ans)


### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  
  if 0 in A:
    print(0)
    return
  
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
  
main()
### BUGGY CODE ###

from time import time

start = time()
D = int(input())
C = [int(i) for i in input().split()]
scores = [[int(i) for i in input().split()] for j in range(D)]
t = []
for i in scores:
    t.append(i.index(max(i))+1)
DC = [0]*26

def calcScore(t):
    score = []
    S = 0
    last = [0]*26
    for d in range(1,D+1):
        S += scores[d-1][t[d-1]-1]
        last[t[d-1]-1] = d
        for i in range(26):
            S -= C[i] * (d - last[i])
            DC[i] += (d - last[i])
        score.append(S)
    return score[-1]

ts = calcScore(t)
i = 0
j = 1
while time() - start < 2:
    d,q = i, j
    temp = [t[i] if d-1 != i else q for i in range(D)]
    j += 1
    if calcScore(temp) > ts:
        t = temp
        i += 1
        j = 0

print("\n".join(map(str, t)))

### FIXED CODE ###

D = int(input())
C = [int(i) for i in input().split()]
scores = [[int(i) for i in input().split()] for j in range(D)]

for i in scores:
    print(i.index(max(i))+1)
### BUGGY CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for i in range(n):
    ans1 = 0
    ans2 = 0
    ok = -1
    ng = n
    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        if a[mid] < b[i] :
            ok = mid
        else:
            ng = mid
        if abs(ng - ok) == 1:
            ans1 += ok + 1
    ok = n
    ng = -1
    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        if b[i] < c[mid]:
            ok = mid
        else:
            ng = mid
        if abs(ng - ok) == 1:
            ans2 += n - ok
    ans += ans1 * ans2
print(ans)

### FIXED CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for i in range(n):
    ans1 = 0
    ans2 = 0
    ok = -1
    ng = n
    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        if a[mid] < b[i] :
            ok = mid
        else:
            ng = mid
        if abs(ng - ok) == 1:
            ans1 += ok + 1
    ok = n
    ng = -1
    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        if b[i] < c[mid]:
            ok = mid
        else:
            ng = mid
        if abs(ng - ok) == 1:
            ans2 += n - ok
    ans += ans1 * ans2
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
x=[int(x) for x in range(1,N+1)]
l=[]
a=0
for i in range(M):
    L,R=map(int,input().split())
    y=list(range(L,R+1))
    l+=y
for j in range(1,N+1):
    if l.count(x[j-1])==M:
        a+=1
print(a)

### FIXED CODE ###

N,M=map(int,input().split())
l=[]
r=[]
for i in range(M):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
a=max(l)
b=min(r)
x=list(range(a,b+1))
print(len(x))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

divisors = {}
def findDivisors(M):
    if M in divisors:
        return divisors[M]
    else:
        divisors[M] = [i for i in range(1, M + 1) if M % i == 0]
        return divisors[M]

def f(N, M):
    if N == 2:
        return len(findDivisors(int(M)))
    else:
        return sum([f(N-1, M / i) for i in findDivisors(int(M))])

def main():
    N, M = map(int, input().split())
    print(f(N, M) % (10 ** 9 + 7))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import functools


def mmul(a, b, mod):
    return (a % mod) * (b % mod) % mod


def mfact(a, mod):
    fact = 1
    for m in range(a + 1):
        fact *= m % mod
        fact %= mod
    return fact


def mpow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a % mod
    if b % 2 == 0:
        return mpow(a, b / 2, mod) ** 2 % mod
    return mpow(a, b // 2, mod) ** 2 * a % mod


def mdiv(a, b, mod):
    return mmul(a, mpow(b, mod - 2, mod), mod)


# (n+a)Ca = (n+a)! / n!a! mod mod for n >> a
def mnpaca(n, a, mod):
    res = 1
    for num in range(n + 1, n + a + 1):
        res *= num % mod
        res %= mod
    return mdiv(res, math.factorial(a), mod)


mod = 10 ** 9 + 7

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

prime_counts = []
i = 2
while i * i <= M:
    count = 0
    while M % i == 0:
        M /= i
        count += 1
    if count:
        prime_counts.append(count)
    i += 1
if M > 1:
    prime_counts.append(1)

res = functools.reduce(lambda x, y: x * y, [mnpaca(N - 1, c, mod) for c in prime_counts], 1)

print(res % mod)
### BUGGY CODE ###

n = int(input())

ans = 0
for a in range(1, n):
    for b in range(1, n):
        if a*b <= n-1:
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

n = int(input())

count = 0
for a in range(1, n):
    for b in range(1, a+1):
        if a * b <= n - 1:
            if a == b:
                count += 1
            else:
                count += 2
        else:
            break
print(count)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if l[i] < l[j] + l[k] and l[j] < l[i] + l[k] and l[k] < l[j] + l[i]:
                ans += 1
print(ans)


### FIXED CODE ###

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

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

li = [i for i in range(A, B+1) if i-A < K or B-i < K]

for i in li:
    print(i)

### FIXED CODE ###

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

li = [i for i in range(A, A+K) if i <= B]
li = li + [i for i in range(B-K+1,B+1) if i >= A]

for i in sorted(set(li)):
    print(i)
### BUGGY CODE ###

# A,B,K = map(int, open(0).read().split())
A,B,K = map(int, input().split())
intList = [i for i in range(A,B+1)]
ansList = set(intList[:K]+intList[::-1][:K])
# print(intList)
# print(ansList)
for j in sorted(ansList):
    print(j)

### FIXED CODE ###

# A,B,K = map(int, open(0).read().split())
A,B,K = map(int, input().split())
r=range(A,B+1)
for j in sorted(set(r[:K])|set(r[::-1][:K])):
    print(j)
### BUGGY CODE ###

def odd(S):
    SS=""
    for i in range(len(S)):
        SS+=S[-i-1]
    return SS

def even(S,F,C):
    if F==1:
        C+=S
        return C
    else:
        S+=C
        return S

S=input()
Q=int(input())

for i in range(Q):
    T=list(map(str,input().split()))
    if len(T)==1:
        temp=odd(S)
        S=temp
    else:
        temp=even(S,int(T[1]),T[2])
        S=temp
        
print(S)

### FIXED CODE ###

S=input()
Q=int(input())
c=0
left=""
right=""
for i in range(Q):
    T=list(map(str,input().split()))
    if len(T)==1:
        c+=1
    else:
        if (T[1]=="1" and c%2==0) or (T[1]=="2" and c%2==1):
            left+=T[2]
        else:
            right+=T[2]

if c%2==0:
    ans=left[::-1]+S+right
else:
    ans=right[::-1]+S[::-1]+left
print(ans)
### BUGGY CODE ###

n = int(input())
DIV=10**9+7
s=1
for i in range(1,n+1):
    s*=i
print(s%DIV)

### FIXED CODE ###

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

S = input()

s1 = ''
s2 = ''
for i in range(len(S)):
	if i % 2 == 0:
		s1 += '0'
		s2 += '1'
	else:
		s1 += '1'
		s2 += '0'
dif1 = 0
dif2 = 0
for i in range(len(S)):
	if S[i] != s1[i]:
		dif1 += 1
	if S[i] != s2[i]:
		dif2 += 1

print(min([dif1, dif2]))

### FIXED CODE ###

S = input()

dif1 = 0
dif2 = 0

for i in range(len(S)):
	if i%2 == 0 and S[i] == '0':
		dif1 += 1
	if i%2 == 1 and S[i] == '1':
		dif1 += 1
	if i%2 == 0 and S[i] == '1':
		dif2 += 1
	if i%2 == 1 and S[i] == '0':
		dif2 += 1

print(min([dif1, dif2]))
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
ABC= []
for _ in range(N):
    a,b = map(int,input().split())
    ABC.append([a,b])

taka = 0
aoki = 0
while ABC:
    ABC.sort(key=lambda x:[x[0],x[1]])
    taka += ABC.pop()[0]
    if len(ABC)==0:
        break
    ABC.sort(key=lambda x:[x[1],x[0]])
    aoki += ABC.pop()[1]
print(taka-aoki)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
ABC= []
for _ in range(N):
    a,b = map(int,input().split())
    ABC.append([a,b,a+b])

taka = 0
aoki = 0
ABC.sort(key=lambda x:x[2])
while ABC:
    
    taka += ABC.pop()[0]
    if len(ABC)==0:
        break
    aoki += ABC.pop()[1]
print(taka-aoki)
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 1):
    for j in range(i + 1, n):
        k = j + j - i

        if k >= n:
            continue

        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 1):
    for j in range(i + 1, n):
        k = j + j - i

        if k >= n:
            break

        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        else:
            X[i] += X[n] 
            dfs(n, i)
dfs(-1,0)
for i in range(N):
    print(X[i], end=" ")
        

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
 
n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]
 
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
for _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b
 
def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)
### BUGGY CODE ###


def D_160():
    N, X, Y = map(int, input().split())
    count_list = [[0]*N for i in range(N)]
    for i in range(0,N):
        for j in range(i,N):
            count_list[i][j] = min(j-i,abs(X-1-i) + abs(j-(Y-1)) + 1)
    
    #print(count_list)
    count_list = sum(count_list,[])
    
    for i in range(1,N):
        print(count_list.count(i))

D_160()

### FIXED CODE ###


def D_160():
    N, X, Y = map(int, input().split())
    #count_list = [[0]*N for i in range(N)]
    ans = [0 for i in range(N-1)]
    for i in range(0,N):
        for j in range(1+i,N):
            ans_i = min(j-i,abs((X-1)-i) + abs(j-(Y-1)) + 1)
            ans[ans_i-1] += 1
    
    
    for i in ans:
        print(i)

D_160()
### BUGGY CODE ###

n, a, b = map(int, input().split())
N = 2**n - 1
import math
def combinations_count(m, r):
  return math.factorial(m) // (math.factorial(m - r) * math.factorial(r))
A = combinations_count(n, a)
B = combinations_count(n, b)
if a == b:
  print((N-A) % (10**9 + 7))
else:
  print((N-A-B) % (10**9 + 7))

### FIXED CODE ###

def ncr(n, r, p): 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den, p - 2, p)) % p
  
p = 10**9+7
n,a,b = map(int,(input().split()))

bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)
### BUGGY CODE ###

N = int(input())

for _ in range(N):
    x = input()
    y = input()
    m, n = len(x), len(y)
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
                
    print(dp[m][n])

### FIXED CODE ###

def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

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

N = int(input())
A_array = map(int, input().split())
B_array = map(int, input().split())

AB_use = []
BA_use = []
for a, b in zip(A_array, B_array):

    if a > b:
        BA_use.append((b, a))

    elif b > a:
        AB_use.append((a, b))

ans = N

if len(AB_use):
    ans_array = [0] * (ans + 1)
    for i in range(1, ans + 1):
        ans_max = ans_array[i - 1] + 1
        for j in AB_use:
            w, v = j
            if w <= i:
                ans_max = max(ans_max, ans_array[i - w] + v)
        ans_array[i] = ans_max
    # print(ans_array)
    ans = ans_array[ans]


if len(BA_use):
    ans_array = [0] * (ans + 1)
    for i in range(1, ans + 1):
        ans_max = ans_array[i - 1] + 1
        for j in BA_use:
            w, v = j
            if w <= i:
                ans_max = max(ans_max, ans_array[i - w] + v)
        ans_array[i] = ans_max
    ans = ans_array[ans]
    # print(ans_array)
print(ans)

### FIXED CODE ###

N = int(input())
A_array = map(int, input().split())
B_array = map(int, input().split())

AB_use = []
BA_use = []
for a, b in zip(A_array, B_array):

    if a > b:
        BA_use.append((b, a))

    elif b > a:
        AB_use.append((a, b))

ans = N

if len(AB_use):
    if len(AB_use) == 1:
        w, v = AB_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        ans_array = [0] * (ans + 1)
        for i in range(1, ans + 1):
            ans_max = ans_array[i - 1] + 1
            for j in AB_use:
                w, v = j
                if w <= i:
                    ans_max = max(ans_max, ans_array[i - w] + v)
            ans_array[i] = ans_max
        # print(ans_array)
        ans = ans_array[ans]


if len(BA_use):
    if len(BA_use) == 1:
        w, v = BA_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        ans_array = [0] * (ans + 1)
        for i in range(1, ans + 1):
            ans_max = ans_array[i - 1] + 1
            for j in BA_use:
                w, v = j
                if w <= i:
                    ans_max = max(ans_max, ans_array[i - w] + v)
            ans_array[i] = ans_max
        ans = ans_array[ans]
        # print(ans_array)
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
check = set(A + [a - 1 for a in A] + [a + 1 for a in A])
ans = 0
for v in check:
    count = 0
    for a in A:
        if v - 1 <= a <= v + 1:
            count += 1
    ans = max(count, ans)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 0
start, end = min(A), max(A) + 1
for v in range(start, end):
    ans = max(C[v - 1] + C[v] + C[v + 1], ans)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans_list=[]
for i in range(n-k+1):
    a = 0
    for j in range(k):
        a += (1+p[i+j])/2
    ans_list.append(a)
    
ans_list.sort(reverse=True)
print(ans_list[0])

### FIXED CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]
ans_list = [0]
a = 0
ans = 0
ans_ = 0
for i in range(n):
    a += (1+p[i])/2
    ans_list.append(a)
for i in range(n-k+1):
    ans_ = ans_list[i+k]-ans_list[i]
    ans = max(ans, ans_)
    
print(ans)
### BUGGY CODE ###

N=int(input())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
need=[(0,0)]
now=0
for i in range(N-1):
    now+=T[i]
    need.append((now,min(V[i],V[i+1])))
need.append((now+T[N-1],0))
TN=need[N][0]
res=[float('inf')]*(2*TN+1)
for i in range(2*TN+1):
    now=0.5*i
    for j in range(N+1):
        if j>0:
            if need[j-1][0]<=now<=need[j][0]:
                res[i]=min(res[i],V[j-1])
        res[i]=min(res[i],need[j][1]+abs(need[j][0]-now))
ans=0
for i in range(2*TN):
    ans+=0.25*(res[i]+res[i+1])
print(ans)

### FIXED CODE ###

N=int(input())
now=0
T=list(map(int,input().split()))
for i in range(1,N):
    T[i]+=T[i-1]
T=[-1*float('inf'),0]+T+[float('inf')]
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(T[-2]+1)
for t in range(len(vt)):
    now=t
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    if abs(vt[i+1]-vt[i])==1:
        ans+=0.5*(vt[i]+vt[i+1])
    elif vt[i+1]==vt[i]:
        for k in range(N+2):
            if T[k]<=i and i+1<=T[k+1]:
                vv=V[k]
                break
        if vv>vt[i]:
            ans+=0.5*(vt[i]*2+0.5)
        else:
            ans+=vt[i]
print(ans)
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    K=int(input())
    KK=[i for i in range(1,K+1)]
    from functools import reduce
    from math import gcd

    I=list(product(KK,repeat=3))
    for i in I:
        S=list(i)
        ans+=reduce(gcd,S)
    print(ans)


resolve()

### FIXED CODE ###

from itertools import combinations_with_replacement
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    K=int(input())
    KK=[i for i in range(1,K+1)]
    from functools import reduce
    from math import gcd

    I=list(combinations_with_replacement(KK,3))
    for i in I:
        ls=len(set(i))
        if ls==1:
            ans+=reduce(gcd,i)
        elif ls == 2:
            ans+=reduce(gcd,i)*3
        else:
            ans+=reduce(gcd,i)*6





    print(ans)


resolve()
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
sumpro = 0
x = 0
for i in range(n-1):
    x = 0
    for j in range(i+1, n):
        x += a[j]
    sumpro += (a[i]* x)%mod
        
print(sumpro%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
mod = pow(10, 9) + 7
d = []
d.append([1 for _ in range(M + 1)])
d[0][0] = 0

for i in range(0, N - 1):
    d.append([])
    for j in range(M + 1):
        d[i + 1].append(sum([d[i][int(j / k)] for k in range(1, j + 1) if j % k == 0]) % mod)
   
print(d[-1][-1])

### FIXED CODE ###

import collections
N, M = map(int, input().split())
mod = pow(10, 9) + 7

def prime_factorize(K):
    ans = []
    i = 2
    while i ** 2 <= K:
        if K % i == 0:
            K //= i
            ans.append(i)
        else:
            i += 1
    if K != 1:
        ans.append(K)
    
    return ans

def combination(N, r):
    ans = N
    for i in range(1, r):
        ans *= ((N - i) % mod) * pow(i + 1, mod - 2, mod)
        ans %= mod
    
    return ans

prime_nums = dict(collections.Counter(prime_factorize(M)))

ans = 1
for num in prime_nums.values():
    ans *= combination(N - 1 + num, num)
    ans %= mod

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

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

dicts = {}
for tmp in a:
  if tmp in dicts.keys():
    dicts[tmp] += 1
  else:
    dicts[tmp] = 1
    
m = int(input())
result = 0
for key, value in dicts.items():
  result += key*value

for _ in range(m):
  b,c = list(map(int, input().split()))
  if b in dicts.keys():
    tmp = dicts[b]
    del dicts[b]
    if c in dicts.keys():
      dicts[c] += tmp
    else:
      dicts[c] = tmp
    result = 0
    for key, value in dicts.items():
      result += key*value
    print(result)
  else:
    print(result)
  

### FIXED CODE ###

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

dicts = {}
for tmp in a:
  if tmp in dicts.keys():
    dicts[tmp] += 1
  else:
    dicts[tmp] = 1
    
m = int(input())
result = 0
for key, value in dicts.items():
  result += key*value

for _ in range(m):
  b,c = list(map(int, input().split()))
  if b in dicts.keys():
    tmp = dicts[b]
    diff = dicts[b]*b
    add = tmp*c
    
    del dicts[b]
    if c in dicts.keys():
      dicts[c] += tmp
      
    else:
      dicts[c] = tmp
      
    result -= diff
    result += add
    print(result)
  else:
    print(result)
### BUGGY CODE ###

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

l = []
for i in range(n):
    hoge = A.index(min(A))
    l.append(hoge+1)
    A[hoge] = n+1

for i in l:
    print(i, end=' ')

### FIXED CODE ###

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

l = [0] * n
for i, x in enumerate(A):
    l[x-1] = i+1
for i in l:
    print(i, end=' ')
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
lr=[list(map(int, input().split())) for _ in range(q)]
for i in range(q):
  x=s[lr[i][0]-1:lr[i][1]]
  print(x.count('AC'))

### FIXED CODE ###

n,q=map(int,input().split())
s=str(input())
lr=[list(map(int, input().split())) for _ in range(q)]
l=[0]*n
count=0
for i in range(1,n):
  if s[i-1]=='A' and s[i]=='C':
    count+=1
  l[i]=count
for i in range(q):
  print(l[lr[i][1]-1]-l[lr[i][0]-1])