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

import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    def kenkenpa(v):
        return (v3 for v1 in G[v] for v2 in G[v1] for v3 in G[v2])
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            if v==t:
                return step+1
            if v not in visited:
                heapq.heappush(que,(step+1,v))
                visited.add(v)
    return -1
  
print(sol())

### FIXED CODE ###

import heapq
def sol(inp=input):
    s=3
    n,m=map(int,inp().split())
    G={(i+1,j):set() for i in range(n) for j in range(s)}
    for _ in range(m):
        u,v=map(int,inp().split())
        for i in range(s):
            G[(u,i)].add((v,(i+1)%s))
    s,t=map(int,inp().split())
    visited={(s,0)}
    que=[]
    heapq.heappush(que,(0,(s,0)))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in G[u]:
            if v not in visited:
                visited.add(v)
                heapq.heappush(que,(step+1,v))
            if v==(t,0):
                return (step+1)//3
    return -1
print(sol())
### BUGGY CODE ###

import math
n=int(input())
number=list(map(int,input().split()))
SUM=[]
sum=0
x=math.factorial(n)
for i in range(1,n+1):
  sum+= x//i
  sum=sum%(10**9 +7)
  sum= sum%(10**9 +7)
  SUM.append(sum)
ans=0
for i in range(n):
  ans+= number[i]*(SUM[n-1-i]+SUM[i]-x)
  ans=ans%(10**9 +7)
print(ans)

### FIXED CODE ###

import math
n=int(input())
number=list(map(int,input().split()))
SUM=[]
sum=0
p=10**9 +7
x=math.factorial(n)%(10**9 +7)
for i in range(1,n+1):
  k=pow(i,p-2,p)
  sum+= (x*k)%p
  sum= sum%(p)
  SUM.append(sum)
ans=0
for i in range(n):
  ans+= number[i]*(SUM[n-1-i]+SUM[i]-x)
  ans=ans%(p)
print(ans)
### BUGGY CODE ###

N,Q,S,*L = open(0).read().split()
N,Q = int(N),int(Q)
ans = N
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  i = s
  p = S[i]
  for t,d in zip(*[iter(L)]*2):
    if p!=t:
      continue
    if d=='L':
      if i==0:
        l = s
        break
      i -= 1
      p = S[i]
    else:
      if i==N-1:
        r = s
        break
      i += 1
      p = S[i]
  else:
    r = s
ans -= r
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  i = s
  p = S[i]
  for t,d in zip(*[iter(L)]*2):
    if p!=t:
      continue
    if d=='L':
      if i==0:
        l = s
        break
      i -= 1
      p = S[i]
    else:
      if i==N-1:
        r = s
        break
      i += 1
      p = S[i]
  else:
    l = s

ans -= N-r  
print(ans)

### FIXED CODE ###

N, Q, S, *L = open(0).read().split()
N = int(N)
Q = int(Q)
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if m<=-1:
      l = s
      break
    if N<=m:
      r = s
      break
    p = S[m]
  else:
    r = s
ans = l+1
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if N<=m:
      r = s
      break
    if m<=-1:
      l = s
      break
    p = S[m]
  else:
    l = s

ans += N-r
print(N-ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

from collections import Counter
n = int(input())
S = []
r = -n
for i in range(n):
    s = Counter(input())
    S.append(s)
    r += S.count(s)
print(r)

### FIXED CODE ###

import sys
from collections import Counter

n, *S = sys.stdin.read().split()
n = int(n)

def main():
    t = [''.join(sorted(t)) for t in S]
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v*(v-1)
    print(cnt//2)

main()
### BUGGY CODE ###

import numpy as np
X,Y,Z,K = map(int,input().split())
#A = np.empty(X,dtype=int)
#B = np.empty(Y,dtype=int)
#C = np.empty(Z,dtype=int)
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))
A.sort()
B.sort()
C.sort()

AB = [ a+b for a in A for b in B] 
AB.sort()
AB = AB[::-1]
AB= AB[:3000]
ABC = [ab+c for ab in AB for c in C]
ABC.sort()
ABC = ABC[::-1]
for i in range(K):
  print(ABC[i])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
#A = np.empty(X,dtype=int)
#B = np.empty(Y,dtype=int)
#C = np.empty(Z,dtype=int)
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = [ a+b for a in A for b in B]
AB = sorted(AB, reverse=True)
AB = AB[:3000]
ABC = [ab+c for ab in AB for c in C]
ABCs = sorted(ABC, reverse=True)[:K]
for i in range(K):
  print(ABCs[i])
### BUGGY CODE ###

s = input()
t = len(s)

m = [0]
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m.append(a)

n = sorted(m)

c = 0
d = 0

for i in range(t-1):
    if n[i] == n[i+1]:
        c += 1
        d += c
    else:
        c = 0

print(d)


### FIXED CODE ###

s = input()
t = len(s)

x = []
y = 0

while 10 ** y % 2019 not in x:
    x.append(10 ** y % 2019)
    y += 1

z = len(x)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += x[(t-i-1) % z] * (int(s[i]) % 2019)
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))
# print(p)
print(sum(p))
### BUGGY CODE ###

import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

MOD = K * 2
grid = np.zeros((MOD, MOD))


def draw(sx, sy, ex, ey):
    sx %= MOD
    sy %= MOD
    ex = (ex - 1) % MOD + 1
    ey = (ey - 1) % MOD + 1

    if sx < ex and sy < ey:
        grid[sx, sy] += 1
        if ex < MOD:
            grid[ex, sy] -= 1
        if ey < MOD:
            grid[sx, ey] -= 1
        if ex < MOD and ey < MOD:
            grid[ex, ey] += 1

    elif ex <= sx:
        if ey <= sy:
            draw(0, 0, ex, ey)
            draw(0, sy, ex, MOD)
            draw(sx, 0, MOD, ey)
            draw(sx, sy, MOD, MOD)
        else:
            draw(0, sy, ex, ey)
            draw(sx, sy, MOD, ey)
    else:
        draw(sx, 0, ex, ey)
        draw(sx, sy, ex, MOD)


for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K

    # 黒マスをどこに置けばこの条件を満たすか
    # 累積和とったときに条件を満たす範囲だけ +1 されるように調整
    draw(x, y, x + K, y + K)
    draw(x + K, y + K, x + K * 2, y + K * 2)
print(int(grid.cumsum(axis=0).cumsum(axis=1).max()))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = map(int, next(sys.stdin).split())

MOD = K * 2
grid = [[0 for _ in range(MOD)] for _ in range(MOD)]


def draw(sx, sy, ex, ey):
    sx %= MOD
    sy %= MOD
    ex = (ex - 1) % MOD + 1
    ey = (ey - 1) % MOD + 1

    if sx < ex and sy < ey:
        grid[sx][sy] += 1
        if ex < MOD:
            grid[ex][sy] -= 1
        if ey < MOD:
            grid[sx][ey] -= 1
        if ex < MOD and ey < MOD:
            grid[ex][ey] += 1

    elif ex <= sx:
        if ey <= sy:
            draw(0, 0, ex, ey)
            draw(0, sy, ex, MOD)
            draw(sx, 0, MOD, ey)
            draw(sx, sy, MOD, MOD)
        else:
            draw(0, sy, ex, ey)
            draw(sx, sy, MOD, ey)
    else:
        draw(sx, 0, ex, ey)
        draw(sx, sy, ex, MOD)


for _ in range(N):
    x, y, c = next(sys.stdin).split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K

    # 黒マスをどこに置けばこの条件を満たすか
    # 累積和とったときに条件を満たす範囲だけ +1 されるように調整
    draw(x, y, x + K, y + K)
    draw(x + K, y + K, x + K * 2, y + K * 2)

for i in range(MOD - 1):
    for j in range(MOD):
        grid[i + 1][j] += grid[i][j]
for i in range(MOD - 1):
    for j in range(MOD):
        grid[j][i + 1] += grid[j][i]
ans = 0
for i in range(MOD):
    ans = max(ans, *grid[i])
print(ans)
### BUGGY CODE ###

n = int(input())
a = input().split(" ")
order = ""
for i in range(n):
  for j in range(n):
    if a[j] == str(i+1):
      order += str(j+1) + " " 
order.rstrip()
print(order)  

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split(" ")))
b = [0]*n
order = ""
for i in range(n):
	b[a[i]-1]= i+1
for i in b:
  order += str(i) + " "
order.rstrip
print(order)
### BUGGY CODE ###

N = int(input())

for i in range(1,3500+1):
    for j in range(1,3500+1):
        h = i
        n = j
        
        low = 1
        high = 3500
        
        if N*n+N*h-4*h*n == 0:
            continue
        if N*h*n % (N*n+N*h-4*h*n) == 0:
            w = -N*h*n // (N*n+N*h-4*h*n)
            if w > 0:
                print(h,n,w)
                exit()
        


### FIXED CODE ###

N = int(input())

for i in range(1,3500+1):
    for j in range(1,3500+1):
        h = i
        n = j
        
        low = 1
        high = 3500
        
        if N*n+N*h-4*h*n == 0:
            continue
        if N*h*n % (N*n+N*h-4*h*n) == 0:
            w = -N*h*n // (N*n+N*h-4*h*n)
            if w > 0:
                print(h,n,w)
                exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    NT=1
    NA=1
    for i in range(N):
        T,A=MI()
        xt=NT//T
        xa=NA//A
        x=min(xt,xa)
        tempT=T*x
        tempA=A*x
        while tempT<NT or tempA<NA:
            tempT+=T
            tempA+=A
        NT=tempT
        NA=tempA
    print(NT+NA)
            

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    NT=1
    NA=1
    for i in range(N):
        T,A=MI()
        xt=(NT+T-1)//T
        xa=(NA+A-1)//A
        x=max(xt,xa)
        NT=T*x
        NA=A*x
    print(NT+NA)
            

main()
### BUGGY CODE ###

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

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

#dp[i+1][j] := i番目までの商品で重さの総和がj以下の最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print(dp[n][w])

### FIXED CODE ###

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

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

dp = [[0 for i in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print(dp[n][w])
### BUGGY CODE ###

#n = int(input())
h,w = list(map(int,input().split()))
s = []
for i in range(h):
    sh = list(input())
    s.append(sh)
#ki = ["n"]*(h*w)    
ki = [[] for i in range(h*w)]
def ichi(a,b):
    return a + b*h
for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            if  a+1 < h and s[a+1][b] == "." :
                ki[ichi(a+1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a+1,b))
            if  a-1 >= 0 and s[a-1][b] == ".":
                ki[ichi(a-1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a-1,b))
            if b-1 >= 0 and s[a][b-1] == ".":
                ki[ichi(a,b-1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b-1))
            if b+1 < w and s[a][b+1] == "." :
                ki[ichi(a,b+1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b+1))
        else:
            pass
for i in range(w*h):
    ki[i] = list(set(ki[i]))
ans = [0]
for i in range(w*h):
    ikeru = [i]
    sumi = []
    kaisuu = [-1]*(w*h)
    kaisuu[i] = 0
    while len(ikeru) > 0:
        j = ikeru.pop(0)
        sumi.append(j)
        for k in range(len(ki[j])):
            if not ki[j][k] in sumi:
                ikeru.append(ki[j][k])
                if kaisuu[ki[j][k]] > kaisuu[j] + 1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1
                elif kaisuu[ki[j][k]] == -1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1 
#        print(i,kaisuu,ikeru)
    ans.append(max(kaisuu))
#print(ans)
print(max(ans))        

### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
s = []
for i in range(h):
    sh = list(input())
    s.append(sh)
ki = [[] for i in range(h*w)]
def ichi(a,b):
    return a + b*h
for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            if  a+1 < h and s[a+1][b] == "." :
                ki[ichi(a+1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a+1,b))
            if  a-1 >= 0 and s[a-1][b] == ".":
                ki[ichi(a-1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a-1,b))
            if b-1 >= 0 and s[a][b-1] == ".":
                ki[ichi(a,b-1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b-1))
            if b+1 < w and s[a][b+1] == "." :
                ki[ichi(a,b+1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b+1))
        else:
            pass
for i in range(w*h):
    ki[i] = list(set(ki[i]))
ans = [0]
for i in range(w*h):
    ikeru = deque([i])
    sumi = []
    kaisuu = [-1]*(w*h)
    kaisuu[i] = 0
    while ikeru:
        j = ikeru.popleft()
        sumi.append(j)
        for k in range(len(ki[j])):
            if ki[j][k] in sumi:
                pass
            else:
                if ki[j][k] not in ikeru:
                    ikeru.append(ki[j][k])
                if kaisuu[ki[j][k]] > kaisuu[j] + 1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1
                elif kaisuu[ki[j][k]] == -1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1 
#        print(i,kaisuu,ikeru)
    ans.append(max(kaisuu))
#print(ans)
print(max(ans))
### BUGGY CODE ###

n = int(input())
a = []
while True:
  try:
    a.append(int(input()))
  except:
    break

for i in range(n):
  tmp = a[i]
  a[i]=0
  print(max(a))
  a[i]=tmp

### FIXED CODE ###

n = int(input())
a = []
while True:
  try:
    a.append(int(input()))
  except:
    break

A = sorted(a,reverse=True)

MAX = A[0]
SMAX = A[1]

for i in range(n):
  if a[i]==MAX:
    print(SMAX)
  else:
    print(MAX)
### BUGGY CODE ###

n, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n-1)]
l.sort()
# print(l)

lq = [list(map(int, input().split())) for _ in range(q)]
lq.sort()
lq_new = []
for i in range(q):
    if i == 0:
        lq_new = [lq[0]]
    else:
        if lq[i][0] == lq[i-1][0]:
            lq_new[-1][1] += lq[i][1]
        else:
            lq_new.append(lq[i])
lq = lq_new

ch = [[] for _ in range(n)]
ad = [[] for _ in range(n)]

for i in range(n-1):
    a, b = l[i][0]-1, l[i][1]-1
    ch[a].append(b)
    ad[b].append(a)
    for x in ad[a]:
        ch[x].append(b)
        ad[b].append(x)

# print(ch)
# print(ad)

ans = [0 for _ in range(n)]
for i in range(len(lq)):
    p, x = lq[i][0]-1, lq[i][1]
    ans[p] += x
    for j in ch[p]:
        ans[j] += x

ans = map(str, ans)
print(" ".join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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

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

ans = [0 for _ in range(n)]

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

checked = [False] * n
checked[0] = True


def function(now, count):
    ans[now] += count
    for i in tree[now]:
        if checked[i] == False:
            checked[i] = True
            function(i, ans[now])

function(0, 0)

for a in ans:
    print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, M = map(int, input().split())
# 文字列の入力
H_list = list(map(int, input().split()))
#print(H_list)
#開業されたN個要素を受け付ける
road_list = []
for i in range(M):
    road_list.append(list(map(int, input().split())))
#print(road_list)
ans = 0
for i in range(N):
    #print(i+1)
    flg = 1
    for road in road_list:
        if i+1 in road:
            if i+1 == road[0] and H_list[road[0]-1] <= H_list[road[1]-1]:
                flg=0
            elif i+1 == road[1] and H_list[road[1]-1] <= H_list[road[0]-1]:
                flg=0
    if flg==1:
        #print("flg")
        ans=ans+1
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, M = map(int, input().split())
# 文字列の入力
H_list = list(map(int, input().split()))
#print(H_list)
#開業されたN個要素を受け付ける
road_list = []
for i in range(M):
    road_list.append(list(map(int, input().split())))
    #road_list.append(input())
#print(road_list)
flg_list=[]
for i in range(N):
    flg_list.append(1)

#print(flg_list)

ans = 0
'''
for i in range(N):
    #print(i+1)
    flg = 1
    for road in road_list:
        if i+1 in road:
            if i+1 == road[0] and H_list[road[0]-1] <= H_list[road[1]-1]:
                flg=0
            elif i+1 == road[1] and H_list[road[1]-1] <= H_list[road[0]-1]:
                flg=0
    if flg==1:
        #print("flg")
        ans=ans+1
'''
for road in road_list:
    if H_list[road[0]-1] < H_list[road[1]-1]:
        flg_list[road[0]-1]=0
    elif H_list[road[1]-1] < H_list[road[0]-1]:
        flg_list[road[1]-1]=0
    else:
        flg_list[road[0]-1]=0
        flg_list[road[1]-1]=0
for i in range(N):
    if flg_list[i]==1:
        ans=ans+1


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

k, s = list(map(int, input().split()))
ct = 0
for x in range(k+1):
    for y in range(x, k+1):
        if x + y > s:
            break;
        for z in range(y, k+1):
            if x + y + z == s:
                if x == y and y == z:
                    ct += 1
                elif x != y and y != z:
                    ct += 6
                else:
                    ct += 3
                break;
print(ct)

### FIXED CODE ###

k, s = list(map(int, input().split()))
ct = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            ct += 1
print(ct)
### BUGGY CODE ###

s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]

mod = 10**9+7
mul = 1
dp[0][0] = 1

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(10**keta)) % 13
                #print(amari,i)
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        num = int(s[i])
        for j in range(13):
            amari = (j+(num*(10**keta))) % 13
            #print(keta,amari)
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
    #mul = mul*10%13
            
print(dp[len(s)][5])
#print(dp[len(s)][5])

### FIXED CODE ###

s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]

mod = 10**9+7
mul = 1
dp[0][0] = 1

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(mul)) % 13
                #print(amari,i)
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        num = int(s[i])
        for j in range(13):
            amari = (j+(num*(mul))) % 13
            #print(keta,amari)
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
    mul = mul * 10 % 13
            
print(dp[len(s)][5])
#print(dp[len(s)][5])
### BUGGY CODE ###

N, Q = input().split()
S = input()
for i in range(int(Q)):
    l, r = (int(x) for x in input().split())
    count = 0
    for j in range(r - l):
        if 'AC' == S[j+l-1:j+l+1]:
            count += 1
    print(count)

### FIXED CODE ###

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

AC_appearance = [0] * len(S)
counter = 0
for i in range(1, len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        counter += 1
    AC_appearance[i] = counter 

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

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ASort=sorted(A)
BSort=sorted(B)
g=0
for i in range(N):
    if ASort[i]>BSort[i]:
        g=1
        break
ans=0
if g==0:
    _A=[]
    for i,a in enumerate(A):
        _A.append((i,a))
    _A.sort(key=lambda x:x[1])
    index=[]
    for i in range(N):
        index.append(_A[i][0])
    update=1
    while update:
        update=0
        for i in range(1,N):
            if index[i]<index[i-1]:
                update=1
                buf=index[i-1]
                index[i-1]=index[i]
                index[i]=buf
                ans+=1
if ans>N-2 or g==1:
    print("No")
else:
    print("Yes")



### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.array(list(map(int,input().split())))

AB=np.array([(A[i],B[i]) for i in range(N)])
AB=AB[np.argsort(AB[:,1])]

AI=np.array([[i,AB[i,0]] for i in range(N)])
AI=AI[np.argsort(AI[:,1])]

sigma=AI[:,0]
ASort=AI[:,1]
BSort=AB[:,1]

g=0
f=0
for i in range(N):
    if ASort[i]>BSort[i]:
        g=1
        break

counter=1
start=0
now=sigma[start]
while start!=now:
    now=sigma[now]
    counter+=1
    
if N==counter:
    f=1
    for i in range(N-1):
        if BSort[i]>=ASort[i+1]:
            f=0
            break

if f==0 and g==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

s = input()
t = input()
dp = [[0] * (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] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])

i, j = len(s), len(t)
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (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] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])

i, j = len(s), len(t)
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1
print(ans[::-1])
### BUGGY CODE ###

N = int (input ())
A = [int (x) for x in input().split()]
X = 0
for i in range (N-1):
  for j in range (N-i-1):
    X += A[i]*A[j+i+1]
print (X%(10**9+7))

### FIXED CODE ###

N = int (input ())
A = [int (x) for x in input().split()]
S = sum (A)
X = 0
for i in range (N-1):
  X += A[i]*(S-A[i])
  S -= A[i]
  if X > 10**9+7:
    X = X%(10**9+7)
print (X)