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

n = int(input())
s = input()

count = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            f1 = False
            f2 = False
            p1 = 0
            p2 = 0
            for i in range(0, n-2):
                if int(s[i]) == a:
                    f1 = True
                    p1 = i
                    break
            if f1:
                for j in range(p1+1, n-1):
                    if int(s[j]) == b:
                        f2 = True
                        p2 = j
                        break
            if f2:
                for k in range(p2+1, n):
                    if int(s[k]) == c:
                        count += 1
                        break
print(count)

### FIXED CODE ###

# TLE

n = int(input())
s = input()

count = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            f1 = False
            f2 = False
            p1 = 0
            p2 = 0
            for i in range(0, n-2):
                if int(s[i]) == a:
                    f1 = True
                    p1 = i
                    break
            if f1:
                for j in range(p1+1, n-1):
                    if int(s[j]) == b:
                        f2 = True
                        p2 = j
                        break
            if f2:
                for k in range(p2+1, n):
                    if int(s[k]) == c:
                        count += 1
                        break
            if not f1 or not f2:
                break
print(count)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r):
    # [l,r]
    # return この手番の人 - 次の手番の人
    # if l == r -> return a[l] をmemo[i][i]への代入で済ませてある

    if memo[l * n + r] is None:
        memo[l * n + r] = max(a[r] - func(l, r - 1), a[l] - func(l + 1, r))
    return memo[l * n + r]


n = int(input())
a = tuple(int(x) for x in input().split())

memo = [None] * pow(n, 2)
for i, aa in enumerate(a):
    memo[n * i + i] = aa

print(func(0, n - 1))


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

# 解説AC
MOD = 10**9 + 7


def main():
    S = input()[::-1]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*(10**i))+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*(10**i))+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説AC
MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    d = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*d)+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*d)+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
        d *= 10
        d %= 13
    print(dp[N][5] % MOD)


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

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

H, W = [int(a) for a in input().split()]
S = [None] * H

for i in range(H):
    S[i] = input()

light = [[[0, 0] for _ in range(W)] for _ in range(H)]
ans = 0

# 横を調べる
for i in range(H):
    j = 0
    while j < W:
        horizontal = 0
        while j < W and S[i][j] == '.':
            horizontal += 1
            j += 1
        for jj in range(horizontal):
            light[i][j - 1 - jj][0] = horizontal
        while j < W and S[i][j] == '#':
            j += 1

# 縦を調べる
for j in range(W):
    i = 0
    while i < H:
        vertical = 0
        while i < H and S[i][j] == '.':
            vertical += 1
            i += 1
        for ii in range(vertical):
            light[i - 1 - ii][j][1] = vertical
            ans = max( ans, sum(light[i - 1 - ii][j]) - 1)
        while i < H and S[i][j] == '#':
            i += 1

print(ans)


### FIXED CODE ###

H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]

ans = 0

# L, R, Uを求める
for i in range(H):
    for j in range(W):

        if S[i][j] == '#':
            pass  # L, R, Uは0で初期化されている
        else:
            # Uを求める
            if i == 0:  U[i][j] = 1
            else:       U[i][j] = U[i - 1][j] + 1

            # Lを求める
            if j == 0:  L[i][j] = 1
            else:       L[i][j] = L[i][j - 1] + 1

        # Rを求める
        if S[i][W - 1 - j] == '#':
            pass
        elif j == 0:
            R[i][W - 1 - j] = 1
        else:
            R[i][W - 1 - j] = R[i][W - j] + 1

# Dを求める
for i in range(H - 1, -1, -1):
    for j in range(W):
        if S[i][j] == '#':  pass
        elif i == H - 1:    D[i][j] = 1
        else:               D[i][j] = D[i + 1][j] + 1
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

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

import sys
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

sys.setrecursionlimit(10**8)


def knap(i, j):
    if i == N:
        return 0
    elif j < W[i]:
        return knap(i+1, j)
    else:
        return max(knap(i+1, j), knap(i+1, j - W[i]) + V[i])


print(knap(0, L))


### FIXED CODE ###

N, W = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

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

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

# print(*dp, sep='\n')
print(dp[N][W])
### BUGGY CODE ###

def main():
    h, w, m = map(int, input().split())
    hp = [0]*h
    wp = [0]*w
    hw = []
    for _ in range(m):
        h1, w1 = map(int, input().split())
        hp[h1-1] += 1
        wp[w1-1] += 1
        hw.append([h1, w1])

    h_max = max(hp)
    w_max = max(wp)

    hh = [i+1 for i, v in enumerate(hp) if v == h_max]
    ww = [i+1 for i, v in enumerate(wp) if v == w_max]


    ans = h_max + w_max
    for hb in hh:
        for wb in ww:
            if [hb, wb] not in hw:
                print(ans)
                exit()
    print(ans-1)


if __name__== '__main__':
    main()

### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    hp = [0]*h
    wp = [0]*w
    hw = set()
    for _ in range(m):
        h1, w1 = map(int, input().split())
        hp[h1-1] += 1
        wp[w1-1] += 1
        hw.add((h1, w1))

    h_max = max(hp)
    w_max = max(wp)

    hh = [i+1 for i, v in enumerate(hp) if v == h_max]
    ww = [i+1 for i, v in enumerate(wp) if v == w_max]
    ans = h_max + w_max

    for hb in hh:
        for wb in ww:
            if (hb, wb) not in hw:
                print(ans)
                exit()
    print(ans-1)


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

from collections import deque

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
A=list(map(lambda x: deque(x), A))
#print(A)

ans=0

L=[]
for i in range(N):
  L.append(len(A[i]))
#print(L)

while 1:
  P=[0]*N
  sw=0
  C=[]
  for i in range(N):
    if L[i]:
      if i+1==A[A[i][0]-1][0]:
        P[i]=1
        C.append(i)
        sw=1
  #print(P)
  if sw:
    for c in C:
      if P[c]:
        A[c].popleft()
        L[c]-=1
    ans+=1
  else:
    tmp=0
    for a in A:
      tmp+=len(a)
    if tmp!=0:
      ans=-1
    break
print(ans)
    

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
A = [[]] + [list(map(int, input().split()))[::-1] for _ in range(N)]

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

stack = []
for i in range(1, N + 1):
  a = A[i].pop()
  pair[i][a] += 1
  if pair[i][a] == pair[a][i] == 1:
    stack.append(i)
    stack.append(a)

r = []
answer = 1
while stack:
  while stack:
    i = stack.pop()
    if A[i]:
      a = A[i].pop()
      pair[i][a] += 1
      if pair[i][a] == pair[a][i] == 1:
        r.append(i)
        r.append(a)
  stack = r
  if r:
    answer += 1
  r = []
  
flag = 1
for i in range(1, N + 1):
  if A[i]:
    flag = 0
    break
if flag:
  print(answer)
else:
  print(-1)
### BUGGY CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    l=m//n
    ans=0
    for i in range(1,l+1):
        s=i*(n-1)
        if (m-s)%i==0:
            ans=max(ans,i)

    print(ans)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

def make_divisors(n):
    if n==1:
        divisors=[1]
        return divisors
    else:
        divisors=[]
        for i in range(1,n):
            if i*i>n:
                break
            if n%i==0:
                divisors.append(i)
                if i!=n//i:
                    divisors.append(n//i)

        divisors.sort()
        return divisors

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,M=map(int,readline().split())

    d=make_divisors(M)
    for i in range(len(d)):
        if d[i]-N>=0:
            print(M//d[i])
            break

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

n, k = map(int, input().split())
A = list(map(int, input().split()))
AS = set(A)
B = []
for i in AS:
    B.append(A.count(i))
B.sort()
print(sum(B[:len(AS) - k]))

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
AD = sorted(list(Counter(A).values()))
print(sum(AD[:len(AD) - k]))
### BUGGY CODE ###

S = input()

mods = []
cnt = 0
for i in range(len(S)):
    mod = int(S[i:]) % 2019
    if mod == 0:
        cnt += 1
    else:
        mods.append(mod)

cnt += len(mods) - len(set(mods))
print(cnt)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

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

#dojkstra (prioroty queue ver.)
import queue
G=[]
inf=3*10**15
#V, E=map(int,input().strip().split(' '))
V=int(input().strip())
E=V-1

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

d=[]

for i in range(V):
    d.append(dijkstra(i))

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す
x=[]
y=[]
for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(d[x[i]][K]+d[K][y[i]])

### FIXED CODE ###

import sys
#limit=sys.getrecursionlimit()
sys.setrecursionlimit(10000000)
#sys.setrecursionlimit(1000000000)

V=int(input().strip())
E=V-1
inf=3*10**15
G=[]
dist=[inf]*V

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1])

visited=[False]*V
def dfs(v,p,d):
    #global d
    dist[v]=d
    for q in G[v]:
        if q[1]==p:
            continue
        dfs(q[1],v,d+q[0])

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す

dfs(K,-1,0)

x=[]
y=[]

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])
### BUGGY CODE ###

from sys import stdin

k,s = [int(x) for x in stdin.readline().rstrip().split()]

point = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i + k + j == s:
                point += 1

print(point)

### FIXED CODE ###

from sys import stdin

k,s = [int(x) for x in stdin.readline().rstrip().split()]

point = 0

for i in range(k+1):
    for j in range(k+1):
        if 0<= s-i-j <= k:
            point += 1

print(point)
### BUGGY CODE ###

from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]

sys.setrecursionlimit(10**9)
DP = [0]*(H+1)

for x in range(1,H+1):
    DP[x] = min(DP[max(x-a,0)] + b for a,b in M)

print(DP[H])

### FIXED CODE ###

from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]

sys.setrecursionlimit(10**9)
DP = [0]*(H+1)

for x in range(1,H+1):
    DP[x] = min(DP[max(x-a,0)] + b for a,b in M)

print(DP[H])
### BUGGY CODE ###

s=input()
q=int(input())
for _ in range(q):
	k=input()
	if k == "1":
		s = s[::-1]
	else:
		if k[2] == "1":
			s = k[4:]+s
		if k[2] == "2":
			s = s+k[4:]
print(s)

### FIXED CODE ###

from collections import deque
s=input()
Q=int(input())
hanten = 0
mae = deque()
ushiro = deque()
for i in range(Q):
	q=input()
	if q=="1":
		hanten ^= 1
	else:
		if q[2] == "1":
			if hanten == 0:
				mae.appendleft(q[4])
			else:
				ushiro.append(q[4])
		else:
			if hanten == 0:
				ushiro.append(q[4])
			else:
				mae.appendleft(q[4])
if hanten == 0:
	print("".join(mae) + s + "".join(ushiro))
else:
	print(("".join(mae) + s + "".join(ushiro))[::-1])
### BUGGY CODE ###

N, A = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
sumx = sum(x)
DP = [[[0] * (N+1) for i in range(sumx+1)] for i in range(N+1)]
DP[0][0][0] = 1
for i in range(N):
    for j in range(sumx+1):
        for k in range(i+1):
            if j - x[i] >= 0:
                DP[i+1][j][k+1] += DP[i][j-x[i]][k]
            DP[i+1][j][k] += DP[i][j][k]

res = 0
for i in range(1,N+1):
    if i * A <= sumx:
        res += DP[N][i * A][i]
print(res)

### FIXED CODE ###

N, A = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
sumx = sum(x)
DP = [[[0] * (N+1) for i in range(sumx+1)] for i in range(N+1)]
DP[0][0][0] = 1
for i in range(N):
    for j in range(sumx+1):
        for k in range(i+1):
            if j - x[i] >= 0:
                DP[i+1][j][k+1] += DP[i][j-x[i]][k]
            DP[i+1][j][k] += DP[i][j][k]

res = 0
for i in range(1,N+1):
    if i * A <= sumx:
        res += DP[N][i * A][i]
print(res)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
        i += 1
t = 0
while len(b) != W*H:
    """
    print("<<<< %d >>>>" %(t))
    for h in range(H):
        s = ""
        for w in range(W):
            if h*W+w in b:
                s += "#"
            else:
                s += "."
        print(s)
    """
    t += 1
    tb = []
    for i in b:
        if i-W >= 0:
            tb.append(i-W)
        if i%W > 0:
            tb.append(i-1)
        if i%W < W-1:
            tb.append(i+1)
        if i+W < H*W:
            tb.append(i+W)
    b = list(set(b+tb))
print(t)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)
### BUGGY CODE ###

target = int(input())
 
year = 0
money = 100
while money < target:
  year += 1
  money *= 1.01
  if "." in str(money):
    money = str(money)
    money = money.split(".")
    money = int(money[0])
print(year)

### FIXED CODE ###

import math

target = int(input())
 
year = 0
money = 100
while money < target:
  year += 1
  money *= 1.01
  money = math.floor(money)
print(year)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
limit = 1000000000000000000
ans = 1
for i in range(N):
    ans *= A[i]  
print(ans) if ans <= limit else print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
limit = 1000000000000000000
ans = 1
for i in range(N):
    if A[i] == 0:
        ans = 0

flag = False
for i in range(N):
    ans *= A[i]  
    if ans > limit:
        flag = True
        break
print(-1) if flag else print(ans)
### BUGGY CODE ###

q=int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a=primes(100000)
for i in range(q):
    l,r=map(int,input().split())
    cnt=0
    for j in a:
        if l<=j<=r:
            if (j+1)//2 in a:
                cnt+=1
    print(cnt)


### FIXED CODE ###

import math
p=[0 for k in range(100000)]
p[1]=1
for k in range(3,100000,2):
    f=1
    for l in range(2,int(math.sqrt(k))+1):
        if k%l==0:
            f=0
            break
    if f==1:
        p[k]=1
c=[0 for k in range(100000)]
c[3]=1
for k in range(3,100000,2):
    if p[k] and p[(k+1)//2]:
        c[k]=1
for k in range(1,100000):
    c[k]+=c[k-1]
for k in range(int(input())):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])
### BUGGY CODE ###



def submit():
    s = input()
    t = input()

    # dp[i][j] : sをi、tをjまで見た時のlcs長
    # dp[i + 1][j + 1] = {
    #   dp[i][j] + 1, 
    #   dp[i + 1][j] or dp[i][j + 1]のいずれか
    # }

    dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    
    # 再構成する
    i = len(s)
    j = len(t)
    ans = ""
    while dp[i][j]:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
        else:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print(ans)


submit()

### FIXED CODE ###



def submit():
    s = input()
    t = input()

    # dp[i][j] : sをi、tをjまで見た時のlcs長
    # dp[i + 1][j + 1] = {
    #   dp[i][j] + 1, 
    #   dp[i + 1][j] or dp[i][j + 1]のいずれか
    # }

    dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    
    # 再構成する
    i = len(s)
    j = len(t)
    ans = ""
    while dp[i][j]:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
        else:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print(ans)


submit()
### BUGGY CODE ###

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

    m = 10 ** 9 + 7
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            seki = a[i] * a[j]
            ans += seki % m
            if ans >= m:
                ans = ans % m
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

import collections
N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1

for key, value in A_dict.items():
    ANS=ANS*(key**value)

if ANS>10**18:
    print("-1")
else:
    print(ANS)


### FIXED CODE ###

import collections
import sys

N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
if 0 in A_dict.keys():
    print("0")
    sys.exit()
    
for key, value in A_dict.items():
    ANS=ANS*(key**value)
    if ANS>10**18:
        print(-1)
        sys.exit()

print(ANS)
### BUGGY CODE ###

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

keylist = [[False]*M for _ in range(N)]

for i in range(M):
    L, R = map(int,input().split())
    for j in range(L-1,R):
        keylist[j][i] = True

for i in range(N):
    if all(keylist[i]):
        ans += 1
        
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
ans = 0
L,R = 0, 100000

for i in range(M):
    Ltmp, Rtmp = map(int,input().split())
    L, R = max(L, Ltmp), min(R, Rtmp)

print(max(0,R-L+1))
### BUGGY CODE ###

def findAC(s):
    retSum = 0
    for i in range(len(s)-1):
        if s[i] == "A" and s[i+1] == "C":
            retSum+=1
    return retSum

n,q = map(int,input().split())
s = input()
lr = []
for i in range(q):
    lr.append([int(i) for i in input().split()])
for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    s_q = s[l-1:r]
    print(findAC(s_q))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = []
for i in range(q):
    lr.append([int(i) for i in input().split()])
    
acnum = []
acsum = 0
acnum.append(acsum)
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        acsum +=1
    acnum.append(acsum)
for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    retSum = 0
    print(acnum[r] - acnum[l])