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

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
e = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


def dijkstra(s,cu):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud[cu]:
                d[u] = c + ud[cu]
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
m = 10**15
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
print(ans%mod)


### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    for j in range(i,N+1,i):ans+=j
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for j in range(1,N+1):
    Y = N//j
    ans += Y*(Y+1)*j//2
print(ans)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

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

ans = 0
a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

for x in range(len(a_cum)):
    if a_cum[x] > k:
        break
    for y in range(len(b_cum)):
        if a_cum[x] + b_cum[y] <= k:
            ans = max(ans, x + y)
        else:
            break

print(ans)


### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

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

ans = 0
a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

y = m  # len(b_cum) - 1
for x in range(len(a_cum)):
    if a_cum[x] > k:
        break
    while b_cum[y] > k - a_cum[x]:
        y -= 1
    ans = max(ans, x + y)

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

n = int(input())

sum = 0
for i in range(n):
    sum += i

print(sum)


### FIXED CODE ###

n = int(input())

print((n * (n - 1)) // 2)
### BUGGY CODE ###

import sys
from collections import Counter
from collections import defaultdict
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)

def plus(now,value):
	for i in data[now]:
		if not visited[i]:
			cnt[i]+=value
			visited[i]=1
			# print(cnt)	
			plus(i,cnt[i])
		
		
visited[1]=1
plus(1,cnt[1])
print(*cnt[1:])

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]
	# print(cnt)
# count=0
def plus(now,value,parent):
	for i in data[now]:
		# global count
		# count+=1
		if i==parent:continue
			
		cnt[i]+=value
		visited[i]=1
		# print(cnt)	
		
		plus(i,cnt[i],now)
		
		
visited[1]=1
plus(1,cnt[1],0)
print(*cnt[1:])
# print(count)

# ans=sorted(cnt.items())
# print(*[i[1] for i in ans])
### BUGGY CODE ###

n, m = map(int, input().split())
can_through = ["1" for _ in range(n)]
# cnt = 0

for i in range(m):
    l, r = map(int, input().split())
    # for j in range(1, n+1):
    #     if can_through[j-1]:
    #         if l <= j <= r:
    #             pass
    #         else:
    #             can_through[j-1] = False

    # print(can_through[:2])
    # print(can_through[2:])
    can_through[:l-1] = "0"*(l-1)
    # print(can_through)
    can_through[r:n] = "0"*(n-r)

    # print(can_through)

print(can_through.count("1"))

### 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 ###

# 常備セット
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,wmax = imap()
wv = np.array([iarr() for i in range(n)])
w,v = wv.T[0], wv.T[1]
dp = np.zeros((n+1, wmax+1),dtype=np.int64)

for i in range(n):
    for ww in range(wmax+1):
        dp[i+1][ww] = max(dp[i][ww], dp[i][ww-w[i]]+v[i]) if ww-w[i]>=0 else dp[i][ww]

ans = dp[n][wmax]
print(ans)


### FIXED CODE ###

n,w_lim = map(int,input().split())
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = map(int,input().split())
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 1
dev = 1000000007
for i in range(1, N+1):
  ans*=i
print(ans % dev)


### FIXED CODE ###

N = int(input())
ans = 1
dev = 1000000007
for i in range(1, N+1):
  ans = i * ans % dev
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# A - XOR Circle
def get_caps(a):
  dic = dict()

  for ai in a:
    dic.setdefault(ai, 0)
    dic[ai] += 1

  return dic


def can_put_on_cap(n):
  global caps

  if n in caps.keys():
    if caps[n] > 0:
      caps[n] -= 1
      return True


def get_xor(a, b):
  bin_a = format(a, 'b')
  bin_b = format(b, 'b')

  digit = max(len(bin_a), len(bin_b))

  # 2進数のケタ数を揃える
  bin_a = bin_a.zfill(digit)
  bin_b = bin_b.zfill(digit)
  s = ''

  for i in range(len(bin_a)):
    if bin_a[i] == '0' and bin_b[i] == '1':
      s += '1'
    elif bin_a[i] == '1' and bin_b[i] == '0':
      s += '1'
    else:
      s += '0'

  # 10進数に戻す
  return int(s, 2)


import itertools
import copy

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

# 帽子の情報をdictに入れる
caps_original = get_caps(a)

# 1,3番目のラクダを先に決めておく
combis = list(itertools.combinations(a, 2))

for c in combis:
  caps = copy.deepcopy(caps_original)
  count = 0
  xor = 0

  if can_put_on_cap(c[0]):
    count += 1

    if can_put_on_cap(c[1]):
      camels = [0] * N
      camels[0] = c[0]
      camels[2] = c[1]
      count += 1

      # 2番目のラクダの帽子が決まる
      camels[1] = camels[0] ^ camels[2]

      if can_put_on_cap(camels[1]):
        count += 1

        for i in range(1, N - 2):
          xor = get_xor(camels[i], camels[i + 2])

          if can_put_on_cap(xor):
            camels[i + 1] = xor
            count += 1
          else:
            break

        if count == N:
          if camels[N - 2] ^ camels[0] == camels[N - 1]:
            print('Yes')
            exit()

print('No')

### FIXED CODE ###

def get_caps(a):
  dic = dict()

  for ai in a:
    dic.setdefault(ai, 0)
    dic[ai] += 1

  return dic


def is_match(caps):
  global N

  if 0 in caps.keys():
    if caps[0] == N:
      return True
  
  if N % 3 == 0:
    if 0 in caps.keys() and len(caps) == 2:
      if caps[0] == N//3:
        return True
    elif len(caps) == 3:
      x, y, z = caps.keys()
    
      if x ^ y ^ z == 0:
        if caps[x] == caps[y] == caps[z] == N//3:
          return True


# A - XOR Circle
N = int(input())
a = list(map(int, input().split()))

# 帽子の情報をdictに入れる
caps = get_caps(a)

if is_match(caps):
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            if j < n - 1:
                j += 1
                count += n - j 
            else:
                count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][i] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)



    


### FIXED CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

dic = {}
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if not (S[i],S[j],S[k]) in dic:
                dic[(S[i],S[j],S[k])] = 1

print(len(dic))


### FIXED CODE ###

N = int(input())
S = [int(i) for i in input()]
ans = 0
for i in range(10):
    fp = -1
    for tf in range(N - 2):
        if S[tf] == i:
            fp = tf
            break
    if fp == -1:
        continue

    for j in range(10):
        sp = -1
        for ts in range(fp + 1, N - 1):
            if S[ts] == j:
                sp = ts
                break
        if sp == -1:
            continue

        for k in range(10):
            for tt in range(sp + 1, N):
                if S[tt] == k:

                    ans += 1
                    break

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

def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
for i in range(N):
    tmp = 0
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            s_i += 1
        else:
            tmp += b
            break

    bomb[i] -= tmp
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        for j in range(s_i, len(queue)):
            queue[j][0] += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)


### FIXED CODE ###

from collections import deque


def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
dq = deque()
s_i = 0
sum_q = 0
for i in range(N):
    while dq and dq[0][1] < XH[i][0]:
        b, _ = dq.popleft()
        sum_q -= b

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        dq.append([bomb[i], XH[i][0] + 2 * D])

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


import sys
from collections import defaultdict
from itertools import permutations

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for combination in permutations(range(N), N):
    A = defaultdict(int)
    cost = 0
    for c in combination:
        book = books[c]
        cost += book[0]
        for i in range(1, M + 1):
            A[i] += book[i]
        ok = True
        for i in range(1, M + 1):
            if A[i] < X:
                ok = False
                break
        if ok:
            ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for s in (range(1 << N)):
    A = defaultdict(int)
    cost = 0
    for i in range(N):
        if s >> i & 1:
            book = books[i]
            cost += book[0]
            for i in range(1, M + 1):
                A[i] += book[i]
    ok = True
    for i in range(1, M + 1):
        if A[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
p = list(map(int,input().split()))

m = p[0:K]
for i in range(1,N-K+1):
    if sum(m) < sum(p[i:K+i]):
        m = p[i:K+i]
e = np.array(m)
a = e/2
n = sum(a) + 0.5 * K
print(n)

### FIXED CODE ###

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

s = 0
for i in range(0,K):
    s = s + p[i]
t = s
for j in range(0,N-K):
    u = s + p[j+K] - p[j]
    if u > t:
        t = u
    s = u
print((t+K)/2)
### BUGGY CODE ###

import sys

def can(ab,f,n):
	for i in ab:
		if(i[0]==f and i[1]==n):
			print('POSSIBLE')
			sys.exit()

n,m = map(int,input().split())
ab = []
for i in range(m):
	ab.append(list(map(int,input().split())))
for i in ab:
	if(i[0]==1):
		can(ab,i[1],n)

print('IMPOSSIBLE')




### FIXED CODE ###

import copy
import sys
import math

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = copy.deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			sys.exit()
	print('IMPOSSIBLE')


def listtodict(a):
	b = {}
	for i in a:
		try:
			b[i] += 1
		except:
			b[i] = 1
	return b

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

main()
### BUGGY CODE ###

import sys
# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

S = input().rstrip()
T = input().rstrip()

sn = len(S)
M = [dict() for _ in range(sn)]
for i, s in enumerate(S):
    for j in range(sn):
        M[(i - j + sn) % sn][s] = min(M[(i - j + sn) % sn].get(s, INF), j)
    for j in range(sn):
        if M[(i - j + sn) % sn][s] == 0:
            M[(i - j + sn) % sn][s] = M[(i - j + sn + 1) % sn][s] + 1


ans = 0
idx = sn - 1
for t in T:
    if M[idx].get(t, INF) == INF:
        print(-1)
        sys.exit()
    ans += M[idx][t]
    idx = (idx + M[idx][t]) % sn

print(ans)


### FIXED CODE ###

import sys
import bisect

# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

S = input().rstrip()
T = input().rstrip()

sn = len(S)
d = dict()
for i, s in enumerate(S):
    d[s] = d.get(s, [])
    d[s].append(i)

nowidx = -1
loop = 0
for t in T:
    l = d.get(t, [])
    if len(l) == 0:
        print(-1)
        sys.exit()
    j = bisect.bisect_right(l, nowidx)
    if len(l) <= j:
        nowidx = l[0]
        loop += 1
    else:
        nowidx = l[j]

# print(loop, nowidx)
print(loop * sn + nowidx + 1)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

dp = defaultdict(int)

def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    if dp[(l, r, xl, xr)] > 0 :
        return dp[(l, r, xl, xr)]
    
    ret = min(rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr) for m in range(l + 1, r))
   
    dp[(l, r, xl, xr)] = ret
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])


### FIXED CODE ###

# ikatakosさんの提出を見てlru_cacheなるものを知った。
# まだまだ知らないことがたくさんありますね。

from functools import lru_cache

N = int(input())
A = [int(i) for i in input().split()]

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    return min(rec(l, m, xl, xl+xr)+rec(m, r, xl+xr, xr)+A[m]*(xl+xr) for m in range(l+1, r))
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])
### BUGGY CODE ###

N = int(input())
S = input()
stack = []
cnt = 0
for s in S:
    for i in range(len(stack)):
        if len(stack[i]) <= 2:
            new = s + stack[i]
            if new not in stack:
                stack.append(new)
                if len(new) == 3:
                    cnt += 1
    if s not in stack:
        stack.append(s)
print(cnt)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0

for i in range(10):
    ind_i = S.find(str(i))
    if ind_i != -1:
        S2 = S[ind_i + 1:]
        for j in range(10):
            ind_j = S2.find(str(j))
            if ind_j != -1:
                S3 = S2[ind_j + 1:]
                for k in range(10):
                    cnt_k = S3.count(str(k))
                    if cnt_k > 0:
                        ans += 1


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

S = input()
n = len(S)
mod = 10**9+7
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
mul = 1
for i in range(n):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(k*mul+j)%13] += dp[i][j]
                dp[i+1][(k*mul+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(k*10**i+j)%13] += dp[i][j]
            dp[i+1][(k*10**i+j)%13] %= mod
    mul = (mul*10)%13
print (dp[n][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

from collections import Counter
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
Tcount = Counter(T)
flag = 'YES'
for n,c in Tcount.items():
    if c > D.count(n):
        flag = 'NO'
print(flag)


### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
Tcount = Counter(T)
flag = 'YES'
Dcount = Counter(D)
for n,c in Tcount.items():
    if n not in Dcount:
        flag = 'NO'
        break
    if c > Dcount[n]:
        flag = 'NO'
        break
print(flag)
### BUGGY CODE ###

n,m,q = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(m)]
query = [list(map(int,input().split())) for _ in range(q)]
s = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l,r = lst[i]
    s[l][r] += 1

for i in range(1,n+1):
    for j in range(1,n+1):
        s[i][j] += s[i][j-1]

for i in range(q):
    l,r = query[i]
    ans = 0
    for j in range(l,r+1):
        ans += s[j][r] - s[j][l-1]
    print(ans)

### FIXED CODE ###

n,m,Q = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
lr.sort(key=lambda x:(x[0],x[1]))
ans = [[0]*(n+1) for _ in range(n+1)]
now = 0
for i in range(1,n+1):
  j = 1
  while True:
    if now < m:
      if lr[now][1] == j and lr[now][0] == i:
        ans[i][j] += (ans[i][j]==0)*(ans[i][j-1]) + 1
        now += 1
      else:
        j += 1
        if j <= n:
          ans[i][j] = ans[i][j-1]
        else:
          break
    else:
      j += 1
      if j <= n:
        ans[i][j] = ans[i][j-1]
      else:
        break
ans2 = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    if i == 1:
      ans2[i][j] = ans[i][j]
    else:
      ans2[i][j] = ans2[i-1][j] + ans[i][j]
for i in range(Q):
  p,q = map(int,input().split())
  print(ans2[q][q]-ans2[p-1][q])
### BUGGY CODE ###

n = int(input())
s = input()
secret = []
for i in range(n-2):
        for j in range(i + 1, n - 1): 
                for k in range(j + 1, n): 
                        secret.append(int(s[i] + s[j] + s[k]))
print(len(set(secret)))

### FIXED CODE ###

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

count = 0 
for i in range(1000):
        key = str(i)
        if len(key) == 1:
                key = '00' + key 
        elif len(key) == 2:
                key = '0' + key 
        position_first = s.find(key[0]) 
        if position_first != -1 and position_first < n - 2:
                position_first += 1
                position_second = s[position_first:].find(key[1])
                if position_second != -1 and position_second + position_first < n - 1:
                        position_second += 1
                        position_third = s[position_first + position_second:].find(key[2])
                        if position_third != -1: 
                                count += 1
print(count)