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

def resolve():
    N = int(input())
    S = []
    for _ in range(N):
        s = input()
        S.append(s)
    SS = list(sorted(set(S)))
    count = []
    for i in range(len(SS)):
        count.append(S.count(SS[i]))
    ooki = max(count)
    for j in range(len(SS)):
        if count[j] == ooki:
            print(SS[j])
resolve()

### FIXED CODE ###

count = {}
for i in range(int(input())):
    S = input()
    if S in count:
        count[S] += 1
    else:
        count[S] = 1
ans = max(count.values())
print(*sorted([A[0] for A in count.items() if A[1] == ans]))
### BUGGY CODE ###

n = int(input())
S = []
for _ in range(n):
  s = input()
  S.append(s)
t = []
for i in S:
  l = S.count(i)
  t.append(l)
lm = max(t)
ans = []
for j in S:
  if S.count(j) == lm:
    if j not in ans:
      ans.append(j)
ans.sort()
for k in ans:
  print(k)

### FIXED CODE ###

n=int(input())
d={}
a=[]
for i in range(n):
  s=input()
  if s not in d:
    d[s]=1
    a.append(s)
  else:
    d[s]+=1
m=max(d.values())
a.sort()
for i in a:
  if d[i]==m:
    print(i)
### BUGGY CODE ###

# C - Fennec vs Monster

n, k = map(int, input().split())
h = list(map(int, input().split()))

for i in range(min({k, n})):
    h.remove(max(h))

a = sum(h)
print(a)


### FIXED CODE ###

n, k = map(int, input().split())
h = sorted(list(map(int, input().split())))

if n <= k:
    print(0)
    exit()
else:
    h = h[0:n - k]
    a = sum(h)
    print(a)
### BUGGY CODE ###

n = int(input())

t = n - 1

for i in range(1,n+1):
    if n % i == 0:
        j = n / i
        if t > i + j:
            t = i + j -2

print(int(t))


### FIXED CODE ###

import math
n = int(input())

a = []
m = math.floor(n**(1/2))
for i in range(1,m + 1):
    if n % i == 0:
        a.append(i + (n/i) - 2)

print(int(min(a)))
### BUGGY CODE ###

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


def check(tmp):
    k = 0
    for x, y in zip(A, F):
        t = tmp // y
        if x > t:
            k += x - t
        #k += max(0, x - (tmp // y))
    return(K >= k)


A.sort()
F.sort(reverse=True)

r = A[-1]*F[0]
l = -1

while(r-l > 1):
    tmp = (l+r)//2
    if check(tmp):
        r = tmp
    else:
        l = tmp
print(r)


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                completed=[]
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    completed.append(n)
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and [ny,nx] not in completed:
                            field[ny][nx]=min(field[n[0]][n[1]]+1,field[ny][nx])
                            ans=max(ans,field[ny][nx])
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

h,w=map(int,input().split())
field=[list(input())for i in range(h)]

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="#":
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]
#print(dp)
maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            cnt=0
            queue=[]
            queue.append([y,x])
            while queue:
                ny,nx=queue.pop(0)
                for dy,dx in dydx:
                    nny,nnx=ny+dy,nx+dx
                    if 0<=nny<=h-1 and 0<=nnx<=w-1 and field[nny][nnx]!="#" and ndp[nny][nnx]==1000:
                        ndp[nny][nnx]=ndp[ny][nx]+1
                        queue.append([nny,nnx])
                        if ndp[nny][nnx]>maxi:
                            maxi=ndp[nny][nnx]
            #print(ndp)
print(maxi)
### BUGGY CODE ###

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

h = [-1]
w = [-1]
hw = [[0 for _ in range(W + 1)]for _ in range(H + 1)]

for _ in range(M):
    hi, wi = map(int, input().split())
    h.append(hi)
    w.append(wi)
    hw[hi][wi] = 1

h_cnt = [0] * (H + 1)
w_cnt = [0] * (W + 1)
for i in range(1, M + 1):
    h_cnt[h[i]] += 1
    w_cnt[w[i]] += 1

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []

for i in range(1, H + 1):
    if h_cnt[i] == h_max:
        h_max_idx.append(i)

for i in range(1, W + 1):
    if w_cnt[i] == w_max:
        w_max_idx.append(i)

for i in h_max_idx:
    for j in w_max_idx:
        if hw[i][j] == 0:
            print(h_max + w_max)
            exit()

print(h_max + w_max - 1)


### FIXED CODE ###

from collections import defaultdict


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

h = [-1]
w = [-1]
hw_dict = defaultdict(int)
for _ in range(M):
    hi, wi = map(int, input().split())
    h.append(hi)
    w.append(wi)
    hw_dict[(hi, wi)] = 1
# print(h)
# print(w)
# print(hw)
h_cnt = [0] * (H + 1)
w_cnt = [0] * (W + 1)
for i in range(1, M + 1):
    h_cnt[h[i]] += 1
    w_cnt[w[i]] += 1
# print(h_cnt)
# print(w_cnt)

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []


for i in range(1, H + 1):
    if h_cnt[i] == h_max:
        h_max_idx.append(i)

for i in range(1, W + 1):
    if w_cnt[i] == w_max:
        w_max_idx.append(i)


# print(h_max_idx)
# print(w_max_idx)

ans = 0

for i in h_max_idx:
    for j in w_max_idx:
        tmp = h_cnt[i] + w_cnt[j]
        if hw_dict[(i, j)] == 1:
            tmp -= 1
            ans = max(ans, tmp)
        else:
            ans = tmp
            break

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

from collections import deque

def main():
    h, w = map(int, input().split())
    ls = []
    for _ in range(h):
        ls1 = []
        s = input()
        for i in range(w):
            if s[i] == '.':
                ls1.append(0)
            else:
                ls1.append(1)
        ls.append(ls1)

    def trans(a, b):
        return a * w + b

    ls2 = [[] for _ in range(h * w)]

    for i in range(h):
        for j in range(w):
            # check ij
            if ls[i][j] == 1:
                continue
            if i >= 1 and ls[i-1][j] != 1:
                ls2[trans(i, j)].append(trans(i-1, j))
            if i <= h-2 and ls[i+1][j] != 1:
                ls2[trans(i, j)].append(trans(i + 1, j))
            if j <= w-2 and ls[i][j+1] != 1:
                ls2[trans(i, j)].append(trans(i, j + 1))
            if j >= 1 and ls[i][j-1] != 1:
                ls2[trans(i, j)].append(trans(i, j - 1))


    #print(ls2)


    def route(i, j):
        count = 1
        ss = deque(ls2[i])
        next = deque()
        explored = {i}
        while True:
            if not ss:
                count +=1
                ss = next
                next = deque()
            now =ss.popleft()
            if now in explored:
                continue
            if now == j:
                return count
            else:
                explored.add(now)
                next.extend(ls2[now])
    ans = 0
    for i in range(h * w - 1):
        if ls2[i] == []:
            continue
        for j in range(i+1, h * w):
            if ls2[j] == []:
                continue
            else:
                ans = max(ans, route(i, j))
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    ls = [input() for _ in range(h)]

    def trans(a, b):
        return a * w + b

    ls2 = [[] for _ in range(h * w)]

    for i in range(h):
        for j in range(w):
            # check ij
            if ls[i][j] == '#':
                continue
            if i >= 1 and ls[i-1][j] != '#':
                ls2[trans(i, j)].append(trans(i-1, j))
            if i <= h-2 and ls[i+1][j] != '#':
                ls2[trans(i, j)].append(trans(i + 1, j))
            if j <= w-2 and ls[i][j+1] != '#':
                ls2[trans(i, j)].append(trans(i, j + 1))
            if j >= 1 and ls[i][j-1] != '#':
                ls2[trans(i, j)].append(trans(i, j - 1))


    #print(ls2)


    def route(i):
        count = 1
        ss = deque(ls2[i])
        next = deque()
        explored = {i}
        while ss or next:
            if not ss:
                count +=1
                ss = next
                next = deque()
            now =ss.popleft()
            if now in explored:
                continue
            else:
                explored.add(now)
                next.extend(ls2[now])
        return count-1
    ans = 0
    for i in range(h * w - 1):
        if ls2[i] == []:
            continue
        ans = max(ans, route(i))

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

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)


ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now.append(b)
    #print(nouki, now)
    if now==[]:continue
    m=max(now)
    ans+= m
    now.remove(m)
    

print(ans)
    


### FIXED CODE ###

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
import bisect as bi
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        bi.insort(now,b)
    #print(nouki, now)
    if now==[]:continue
    ans+= now[-1]
    del now[-1]


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

import numpy as np
from numba import njit

@njit('i8(i8,i8[:])', cache=True)
def solve(x,count):
    for i in range(2,x+1):
        count[i:x+1:i] += 1
    return int(np.sum(np.arange(x + 1) * count))

if __name__== "__main__":
    x = int(input())
    count = np.ones(x + 1, dtype=np.int64)
    print(solve(x,count))

### FIXED CODE ###

import numpy as np
from numba import *

@njit('i8(i8,i8[:])', cache=True)
def solve(x,count):
    for i in range(2,x+1):
        for j in range(i,x+1,i):
            count[j] += 1
    return int(np.sum(np.arange(x+1)*count))

if __name__== "__main__":
    x = int(input())
    count = np.ones(x + 1, dtype=np.int64)
    print(solve(x,count))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [[A[i], i] for i in range(N)]
B.sort()
C = [0] * N
cnt = 0
def lsearch(s, t, C):
  if s > t:
    return -1
  if s == t:
    return s if C[s] == 1 else -1
  else:
    m = (s + t) // 2
    return max(lsearch(s, m, C), lsearch(m + 1, t, C))
def rsearch(s, t, C):
  if s > t:
    return len(C)
  if s == t:
    return s if C[s] == 1 else len(C)
  else:
    m = (s + t) // 2
    return min(rsearch(s, m, C), rsearch(m + 1, t, C))
for b, i in B:
  l = i - lsearch(0, i - 1, C)
  r = rsearch(i + 1, N - 1, C) - i
  C[i] = 1
  cnt += b * l * r
print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0] * (N + 1)
for i in range(N):
  B[A[i]] = i + 1
L = list(range(N + 2))
R = list(range(N + 2))
cnt = 0
for i in range(N, 0, -1):
  l = L[B[i]]
  r = R[B[i]]
  cnt += i * (B[i] - l + 1) * (r - B[i] + 1)
  L[r + 1] = l
  R[l - 1] = r
print(cnt)
### BUGGY CODE ###

# python3だとTLE,pypy3だとAC

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0
    for i in range(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


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

s = input()
k = int(input())

s_list = []
for i in range(1, len(s)+1):
    for j in range(0, len(s)-i+1):
        s_list.append(s[j:j+i])

dict_list = list(set(s_list))
dict_list.sort()

print(dict_list[k-1])

### FIXED CODE ###

s = input()
k = int(input())

s_list = []
for i in range(0, len(s)):
    for j in range(1, 1+k):
        if len(s_list) < k:
            s_list.append(s[i:i+j])
            s_list = list(set(s_list))
            s_list.sort()
        elif s_list[k-1] > s[i:i+j]:
            s_list.append(s[i:i+j])
            s_list = list(set(s_list))
            s_list.sort()
            s_list = s_list[:k]
    else:
        continue

dict_list = list(set(s_list))
dict_list.sort()

print(dict_list[k-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

s = input()
x,y = map(int,input().split())
count = 0
d = []
for i in range(len(s)):
    if s[i] == 'F':
        count += 1
    else:
        d.append(count)
        count = 0
if count != 0:
    d.append(count)

dx = [d[i] for i in range(len(d)) if i%2==0]
dy = [d[i] for i in range(len(d)) if i%2==1]

if len(dx) == 0:
    dx = [0]
if len(dy) == 0:
    dy = [0]

def dpx(n,x):
    if n == 1:
        return x == dx[0]
    else:
        return dpx(n-1,x+dx[n-1]) or dpx(n-1,x-dx[n-1])

def dpy(n,y):
    if n == 1:
        return y == dy[0] or y == -dy[0]
    else:
        return dpy(n-1,y+dy[n-1]) or dpy(n-1,y-dy[n-1])

ans = dpx(len(dx),x)&dpy(len(dy),y)
if ans:
    print('Yes')
else:
    print('No')
    

### FIXED CODE ###

s = input()
x,y = map(int,input().split())
count = 0
d = []
s = s.split('T')
d = [len(x) for x in s]

if len(d) == 0:
    d.append(0)
if len(d) == 1:
    d.append(0)
dpx = [d[0]]
dpy = [d[1],-d[1]]
for i in range(2,len(d)):
    di = d[i]
    trans = set()
    if i%2==0:
        for xj in dpx:
            trans.add(xj+di)
            trans.add(xj-di)
        dpx = list(trans)
    else:
        for yj in dpy:
            trans.add(yj+di)
            trans.add(yj-di)
        dpy = list(trans)
ans = (x in dpx)&(y in dpy)

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

import heapq
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x:x[0])
day = 0
pay = 0
q = []
for i in range(1, M+1):
  for j in range(len(ab)):
    if ab[0][0] <= i:
      a, b = ab.pop(0)
      heapq.heappush(q, (-b, a))
    else:
      break
  if len(q) > 0:
    pay += - heapq.heappop(q)[0]

print(pay)


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
day = {i+1: [] for i in range(M)}
for a, b in ab:
  if a <= M:
    day[a] += [-b]
q = []
heapq.heapify(q)
pay = 0
for i in range(M):
  for b in day[i+1]:
    heapq.heappush(q, b)
  if len(q) > 0:
    pay += -heapq.heappop(q)

print(pay)
### BUGGY CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

### FIXED CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
for _a in a:
    result *= _a
if result > 10**18:
    print("-1")
else:
    print(result)

### FIXED CODE ###

int(input())
a = sorted(list(map(int, input().split())))
result = 1
if a[0] == 0:
    print("0")
    exit()
for _a in a:
    result *= _a
    if result > 10**18:
        print("-1")
        exit()
print(result)
### BUGGY CODE ###

from collections import deque

n = int(input())
searching = deque()
searched = deque()


def flatten(data):
    for item in data:
        if hasattr(item, '__iter__'):
            for element in flatten(item):
                yield element
        else:
            yield item


distance_matrix = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    distance_matrix[i][i] = 0
distance_from_one = [0 for _ in range(n)]
tree = [[] for _ in range(n)]

for i in range(n-1):
    array = list(map(int, input().split()))
    x = array[0]
    y = array[1]
    z = array[2]
    distance_matrix[x-1][y-1] = z
    distance_matrix[y-1][x-1] = z
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
for i in tree[0]:
    searching.append(i)
    distance_from_one[i] = distance_matrix[0][i]
searched.append(0)


while len(searching) != 0:
    node = searching.popleft()
    if node not in searched:
        searched.append(node)
        for node_2 in tree[node]:
            if node_2 not in searching and node_2 not in searched:
                distance_from_one[node_2] = distance_from_one[node] + distance_matrix[node][node_2]
                searching.append(node_2)

for i in distance_from_one:
    if i%2 == 0:
        print(1)
    else:
        print(0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
edges = [[] for _ in range(n+1)]
colors = [None] * (n+1)

for i in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    if w & 1 == 0:
        edges[u].append((v, 0))
        edges[v].append((u, 0))
    else:
        edges[u].append((v, 1))
        edges[v].append((u, 1))

colors[1] = 0


def color(node, c):
    colors[node] = c
    for i, j in edges[node]:
        if colors[i] is None:
            new_color = (c + j)%2
            color(i, new_color)

color(1,1)

for i in colors[1:]:
    print(i)
### BUGGY CODE ###

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


a=[]

count_WA=0
for i in range(M):
    a.append(input().split())


AC=[]
for i in a:
    if i[1]=="AC" and not(i[0] in AC):
        AC.append(i[0])
count_AC=len(AC)

for i in a:
    if i[0] in AC:
        if i[1]=="AC":

            AC.remove(i[0])
        else:
            count_WA+=1




print(count_AC,count_WA,sep=" ")


### FIXED CODE ###

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


ac = 0
wa = 0
aclist = {}
walist = {}

count_WA=0
for i in range(N):
    aclist[i + 1] = 0
    walist[i + 1] = 0

for i in range(M):
    a,b=input().split()
    a=int(a)
    if aclist[a] == 1:
        continue
    elif b == 'WA':
        walist[a] += 1
    elif b == 'AC':
        aclist[a] += 1
        ac += 1
        wa += walist[a]




print(ac,wa,sep=" ")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

def main():
    N, M = map(int, input().split())
    edge = [[] * N for _ in range(N)]
    new_edge = [set() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
    
    def dfs(s,now,cnt):
        if cnt == 3:
            if s == now:
                return
            new_edge[s].add(now)
            return

        for v in edge[now]:
            dfs(s,v,cnt+1)
    
    for i in range(N):
        dfs(i,i,0)
    S, T = map(int, input().split())
    S -= 1
    T -= 1
    q = deque([S])
    d = [float('inf')] * N
    d[S] = 0
    while q:
        s = q.popleft()
        if s == T:
            print(d[T])
            exit()
        for v in new_edge[s]: 
            if d[v] != float('inf'):
                continue
            d[v] = d[s] + 1
            q.append(v)

    print(-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    dist = [[float('inf')] * 3 for _ in range(N)]
    dist[S][0] = 0
    q = deque([])
    q.append((S,0))
    while q:
        v, l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if dist[nv][nl] != float('inf'):
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv,nl))
        
    
    if dist[T][0] == float('inf'):
        print(-1)
    else:
        print(dist[T][0] // 3)




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

from collections import defaultdict
import bisect
import numpy as np

MOD = 10 ** 9 + 7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

S_appeared_indices = defaultdict(list)
for i, c1 in enumerate(S):
    S_appeared_indices[c1].append(i)

T_appeared_indices = defaultdict(list)
for j, c2 in enumerate(T):
    T_appeared_indices[c2].append(j)

dp = np.zeros((N+1, M+1), np.int64)
dp[0, :] = 1
dp[:, 0] = 1

for i, c1 in enumerate(S):
    for j, c2 in enumerate(T):
        dp[i+1, j+1] = dp[i+1, j]
        if c2 in S_appeared_indices:
            tmp = bisect.bisect_right(S_appeared_indices[c2], i) - 1
            while tmp >= 0:
                S_index = S_appeared_indices[c2][tmp]
                dp[i+1, j+1] += dp[S_index, j]
                tmp -= 1
        dp[i+1, j+1] %= MOD

print(dp[N, M])

    



### FIXED CODE ###

MOD = 10 ** 9 + 7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

dp = [[1] * (M+1) for _ in range(N+1)]

for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        if s != t:
            dp[i+1][j+1] -= dp[i][j]
        dp[i+1][j+1] %= MOD

print(dp[N][M])