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

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

import itertools as it
import fractions

K = int(input())

gcd_list = []
for i, j, k in it.product(range(1, K+1), range(1, K+1), range(1, K+1)):
    gcd_ = fractions.gcd(fractions.gcd(i, j), k)
    gcd_list.append(gcd_)
print(sum(gcd_list))


### FIXED CODE ###

import itertools as it
import math

K = int(input())

itr = range(1, K+1)
gcd_ = sum([math.gcd(math.gcd(i, j), k)
            for i, j, k in it.product(itr, itr, itr)])
print(gcd_)
### BUGGY CODE ###

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)

cs = []

for _ in range(m):
    b, c = map(int, input().split())
    cs += [c] * b

cs = sorted(cs, reverse=True)

ind_a, ind_c = 0, 0
ans = 0

for i in range(n):
    if len(cs)-1 >= ind_c:
        if a[ind_a] >= cs[ind_c]:
            ans += a[ind_a]
            ind_a += 1
        else:
            ans += cs[ind_c]
            ind_c += 1
    else:
        ans += a[ind_a]
        ind_a += 1

print(ans)

### FIXED CODE ###

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

bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

bc = sorted(bc, key=lambda x: x[1], reverse=True)

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

n = int(input())
tmp = list(map(int, input().split()))
ans = 0
a = sorted(tmp)
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()
double = set(a)
for i in double:
    if not tmp.count(i) == 1:
        ans -= tmp.count(i)

# a.sort()


check = True
loop = list(range(len(a)))
for i in loop:
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)

# ans -= len(set(double))
# ans -= len(double)
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [0] * n ** 2

    for i in range(n):
        dp[i * n + i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[(i + 1) * n + j]
            R = a[j] - dp[i * n + j - 1]
            if L > R:
                dp[i * n + j] = L
            else:
                dp[i * n + j] = R
    return dp[n - 1]


print(solve())


### FIXED CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())
### BUGGY CODE ###

n=int(input());e=[[]for _ in[0]*-~n];q=[(1,0)];f=[-1]*n;exec('v,w,c=map(int,input().split());e[v]+=(w,c),;e[w]+=(v,c),;'*~-n)
while q:
 v,c=q.pop();f[v-1]=c%2
 for w,d in e[v]:q+=[(w,c+d)]*(f[w-1]<0)
print(*f)

### FIXED CODE ###

from collections import*
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for v,w,c in zip(t[::3],t[1::3],t[2::3]):
  e[v-1].append((w-1,c))
  e[w-1].append((v-1,c))
q=deque([(0,0)])
f=[0]+[-1]*~-n
while q:
  v,c=q.pop()
  for w,d in e[v]:
    if-1<f[w]:continue
    d=(c+d)%2
    f[w]=d
    q.append((w,d))
print(*f)
### BUGGY CODE ###

N = int(input())
sticks = list(map(int, input().split()))
sticks.sort()
ans = 0
for a in range(N-2):
  A = sticks[a]
  for b in range(a+1, N-1):
    B = sticks[b]
    c = b+1
    while sticks[c] < A + B:
#      print(A, B, sticks[c])
      c += 1
      ans += 1
      if c == N:
        break
    
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
#print(L)
ans = 0
def find(x, arr):
  a = len(arr)//2
  cur = a
  while True:
    a //= 2
    if arr[cur] < x:
      if cur == len(arr)-1:
        return cur+1
      elif arr[cur+1] >=x:
        return cur+1
      else:
        cur += max(1,a)
    else:
      if cur == 0:
        return 0
      else:
        cur -= max(1, a)
for i in range(N-2):
  for j in range(i+1, N-1):
    ans += find(L[i] + L[j], L)-j-1
print(ans)
### BUGGY CODE ###

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

def compare(item):
  return item[3]

newXL = sorted([[x, l, x-l, x+l] for x, l in XL], key=compare)

memo = [0]

for i in range(N):
  flag = True
  for j in memo:
    if newXL[i][2] < newXL[j][3]:
      flag = False
  if flag:
    memo.append(i)

print(len(memo))

### FIXED CODE ###

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

newXL = sorted([[x-l, x+l] for x, l in XL], key=lambda x:x[1])

previous = 0
total = 1

for i in range(1, N):
  if newXL[i][0] < newXL[previous][1]:
    pass
  else:
    previous = i
    total += 1
    
print(total)
### BUGGY CODE ###

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

bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc += [c] * b

sorted_all = sorted(a + bc, reverse=True)
print(sum(sorted_all[:len(a)]))

### FIXED CODE ###

from collections import Counter

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

abc = Counter(a).most_common()
for i in range(m):
    b, c = map(int, input().split())
    abc.append((c, b))

abc.sort(reverse=True)

ans = 0
count = n
for c, b in abc:
    rep = min(count, b)
    ans += c * rep
    count -= rep
print(ans)
### BUGGY CODE ###

from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
### BUGGY CODE ###

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

ans=1
for i in range(1,N):
    if min(P[:i])>P[i]:
        ans+=1
print(ans)

### FIXED CODE ###

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

ans=1
m=P[0]
for i in range(1,N):
    m=min(m,P[i-1])
    if m>P[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

H,W=map(int, input().split())
M = list( list(input()) for _ in range(H) )

p(H,W)
p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

p(M)

for h in range(H-1):
	for w in range(W-1):
		a=M[h][w]
		if a==0: continue
		
		b=M[h+0][w+1]
		c=M[h+1][w+0]
		d=M[h+1][w+1]
		
		if (b==0)or(b>a+1):
			b=a+1
			M[h][w+1]=b
		
		if (c==0)or(c>a+1):
			c=a+1
			M[h+1][w]=c
		
		if (d==0)or(d>b+1):
			d=b+1
			M[h+1][w+1]=d
		
		if (d==0)or(d>c+1):
			d=c+1
			M[h+1][w+1]=d


for h in range(H-1):
	for w in range(W-1):
		a=M[-1-h][-1-w]
		if a==0: continue

		b=M[-1-h-0][-1-w-1]
		c=M[-1-h-1][-1-w-0]
		d=M[-1-h-1][-1-w-1]
		
		if (b==0)or(b>a+1):
			b=a+1
			M[-1-h-0][-1-w-1]=b

		if (c==0)or(c>a+1):
			c=a+1
			M[-1-h-1][-1-w-0]=c
		
		if (d==0)or(d>b+1):
			d=b+1
			M[-1-h-1][-1-w-1]=d

		if (d==0)or(d>c+1):
			d=c+1
			M[-1-h-1][-1-w-1]=d


p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )



### FIXED CODE ###

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


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

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

import queue
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())

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

points = [0]*N
PX = [list(map(int, input().split())) for _ in range(Q)]
for px in PX:
    points[px[0]-1] += px[1]

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

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

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
L.sort()
L.reverse()
ans = 0
pre = 0
for i in range(n):
    for j in range(i+1, n):
        flag = True
        for k in range(j+1, n):
            if L[i] >= L[j] + L[k]:
                ans += max(0, k - (j + 1))
                flag = False
                break
        if flag:
            ans += n - (j + 1)
print(ans)


### FIXED CODE ###

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

n = int(input())
s = input()
res = 0
for i in range(0, n):
    for j in range(i+1,n):
        if s[i] != s[j]:
            for k in range(j+1,n):
                if j-i!=k-j and s[i] != s[k] and s[j] != s[k]:
                    res += 1

print(res)

### FIXED CODE ###

import collections

n = int(input())
s = input()
res = 0
# for i in range(0, n):
#     for j in range(i+1,n):
#         if s[i] != s[j]:
#             for k in range(j+1,n):
#                 if j-i!=k-j and s[i] != s[k] and s[j] != s[k]:
#                     res += 1
#
# print(res)
num = collections.Counter(s)
# print(num)
num_r = num["R"]
num_g = num["G"]
num_b = n - num_r - num_g
count_2 = 0
for x in range(1,int(n/2)+1):
    for i in range(n-2*x):
        # print(x)
        # print(i)
        # print()
        if (i + 2 * x < n and s[i] != s[i + x] and s[i + x] != s[i + 2 * x] and s[i] != s[i + 2 * x] ):
            count_2 += 1
            # print(x)
            # print(i)
            # print()

res = num_r * num_g * num_b - count_2
# print(num_r)
# print(num_g)
# print(num_b)
print(res)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for i in range (k) :
    for j in range (k) :
        for l in range (k) :
            p = math.gcd(i+1,j+1)
            ans += math.gcd(p,l+1) 
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range (1,k+1) :
    for j in range (1,k+1) :
        p = gcd(i,j)
        for l in range (1,k+1) :
            ans += gcd(p,l)

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

import sys
from collections import deque
from copy import copy
from bisect import bisect_right, bisect_left


N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
BC=[]
for m in range(M):
    b,c = list(map(int, input().split()))
    BC.append([b,c])

BC.sort(key=lambda bc: bc[1], reverse=True)

_sum = 0

for b,c in BC:
    i = bisect_left(A, c)
    if i == 0:
        break
    nrof_replace = min(i,b)
    _sum += c * nrof_replace
    A = A[nrof_replace:]
    
print(_sum + sum(A))


### FIXED CODE ###

import sys
from collections import deque
from copy import copy
from bisect import bisect_right, bisect_left


N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
A = deque(A)
BC=[]
for m in range(M):
    b,c = list(map(int, input().split()))
    BC.append([b,c])

BC.sort(key=lambda bc: bc[1], reverse=True)

_sum = 0

for b,c in BC:
    i = bisect_left(A, c)
    if i == 0:
        break
    nrof_replace = min(i,b)
    _sum += c * nrof_replace
    #A = A[nrof_replace:]
    for i in range(nrof_replace):
        A.popleft()
    
print(_sum + sum(A))
### BUGGY CODE ###

import sys
N, M = map(int, input().split())
ans = N
while True:
   if abs(ans-M) < ans:
        ans = abs(ans-M)
   else:
    print(ans)
    sys.exit()


### FIXED CODE ###

import sys
N, M = map(int, input().split())
ans = N%M
while True:
   if abs(ans-M) < ans:
        ans = abs(ans-M)
   else:
    print(ans)
    sys.exit()
### BUGGY CODE ###

from math import factorial as jj
mod=10**9+7
n,k=map(int,input().split())
l=sorted(map(int,input().split()))
ans=0

ml=jj(n-1)//(jj(k-1)*jj(n-k))
ans-=ml*(l[0]-l[n-1])%mod
for i in range(1,n-k+1):
  ml=ml*(n-i-k+1)//(n-i)
  ans-=ml*(l[i]-l[n-1-i])%mod
print(ans%mod)


### FIXED CODE ###

n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
mod=10**9+7
fact=[1]*(n+1)
inv=[1]*(n+1)
for i in range(2,n+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
for i in range(n):
    if i>=k-1:
        ans+=l[i]*fact[i]*inv[k-1]*inv[i-k+1]%mod
    if n-i-1>=k-1:
        ans-=l[i]*fact[n-i-1]*inv[k-1]*inv[n-i-1-k+1]%mod
    ans%=mod
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]

T = list(set(S))
t = 1
U = []
for i in range(len(T)):
    x = S.count(T[i])
    if t < x:
        t = x
        U = [T[i]]
    elif t == x:
        U.append(T[i])

U_ = list(sorted(U))
for i in range(len(U_)):
    print(U_[i])

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    s = str(input())
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

S = sorted(dic.values())
t = S[-1]

X = []
for key in dic:
    if dic[key] == t:
        X.append(key)
x = sorted(X)

for i in range(len(X)):
    print(x[i])
### BUGGY CODE ###

from sys import stdin

n,q = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
lin = [0]*n
point = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        for k in range(i+1,n):
            lin[k] += 1
for j in range(q):
    print(lin[li[j][1]-1]-lin[li[j][0]-1])

### FIXED CODE ###

from sys import stdin
import bisect

n,q = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
lin = []
point = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        lin.append(i+1)
for j in range(q):
    hi = bisect.bisect(lin,li[j][1]-1)
    lo = bisect.bisect(lin,li[j][0]-1)
    print(hi-lo)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,a,b = map(int, input().split())
h=[int(input()) for i in range(n)]

def solve(num,hit):
    all_b = num*b
    for i in range(len(hit)):
        hit[i] -= all_b
    cnt=0
    for i in range(len(hit)):
        if hit[i]>0:
            cnt+=(hit[i] - 1) // (a-b) + 1
    if cnt <= num:
        return True
    else:
        return False

import copy
l=0
r=10**18
while r-l>1:
    hit = copy.deepcopy(h)
    mid=(l+r)//2

    if solve(mid,hit):
        r=mid
    else:
        l=mid
print(r)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,a,b = map(int, input().split())
h=[int(input()) for i in range(n)]

def solve(num):
    all_b = num*b
    cnt=0
    for i in range(len(h)):
        rest = h[i] - all_b
        if rest>0:
            cnt+=(rest - 1) // (a-b) + 1
    if cnt <= num:
        return True
    else:
        return False

import copy
l=0
r=10**10
while r-l>1:
    mid=(l+r)//2

    if solve(mid):
        r=mid
    else:
        l=mid
print(r)
### BUGGY CODE ###


x = (10**9)+7
n = int(input())
val = 0
lst = list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        val += (lst[i]*lst[j])
        val = val%x
print(val)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
su = sum(arr)
c = 0
for item in arr:
  c+= item*item
print(((su**2 - c)//2)%(10**9 + 7))
### BUGGY CODE ###

N, M = map(int, input().split())
bigp = 10**9+7
L1 = []
L2 = []
p = 2
K = M
while K != 1:
    if K%p == 0:
        L1.append(p)
        K = K//p
        if p not in L2:
            L2.append(p)
    else:
        p = p+1

ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for x in L2:
    primepower = L1.count(x)
    ans *= ModComb(N+primepower-1, primepower, bigp)%bigp

print(ans%bigp)


### FIXED CODE ###

N, M = map(int, input().split())
bigp = 10**9+7
L = []
p, power = 2, 0
K = M
while p*p <= K:
    while K%p == 0:
        K = K//p
        power += 1
    if power > 0:
        L.append([p, power])
    if p == 2:
        p += 1
    else:
        p += 2
    power = 0
if K > 1:
    L.append([K, 1])


ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for i in range(len(L)):
    power = L[i][1]
    ans *= ModComb(N+power-1, power, bigp)
    ans %= bigp

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

n = int(raw_input())
now = n
i = 2
while i <= n and now != 1:
	if now%i == 0:
		n = n*(i-1)/i
		while now%i==0:
			now /= i
	i += 1
print n

### FIXED CODE ###

def phi(n):
	r = n
	i = 2
	while i*i <= n:
		if n%i==0:
			r -= r/i
			while n%i==0:
				n /= i
		i += 1
	if n>1: r-= r/n
	return r

n = int(raw_input())
print phi(n)
### BUGGY CODE ###

import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    s_dict[si] = [i] if si not in s_dict else s_dict[si] + [i]

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = bisect.bisect_left(s_dict[ti], c_in_s)
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')




### FIXED CODE ###

import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    if si not in s_dict:
        s_dict[si] = [i]
    else:
        s_dict[si].append(i)

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = bisect.bisect_left(s_dict[ti], c_in_s)
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')
### BUGGY CODE ###

n = int(input())
a =  [int(input()) for i in range(n)]

for i in range(n):
  b = a.copy()
  b.pop(i)
  print(max(b))

### FIXED CODE ###

import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]
max_a_num = a.count(max(a))
b = sorted(a, reverse=True)
m1, m2 = b[0], b[1]
for i in range(n):
  if max_a_num == 1:
    if a[i] == m1:
      print(m2)
    else:
      print(m1)
  else:
    print(m2)
### BUGGY CODE ###

import math

s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=int(s[1])
t.sort()
for i in range(s[1]):
  for j in range(s[0]):
    if 0<b:
      if max(t)==t[j]:
        t[j]=math.floor(t[j]/2)
        b=b-1
      else:
          continue
    else:
      break
a=sum(t)
print(a)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]

l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    place = A[place]
    K -= 1
    if place in l:
        ind = l.index(place)
        count = len(l) - ind
        print(l[ind + K%count]+1)
        exit()

### FIXED CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]
flag = [False]*N
l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    flag[place]=True
    place = A[place]
    K -= 1
    if flag[place]:
        ind = l.index(place)
        count = len(l) - ind
        print(l[ind + K%count]+1)
        exit()
### BUGGY CODE ###

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

for i in range(1,n+1):
  c = a.count(i)
  print(c)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
lis = [0]*n

for i in a:
  lis[i-1] += 1
  
print(*lis,sep = '\n')