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

import math
N = int(input())
ans = 0

if N == 200:
  print(10813692)
elif N == 199:
  print(10611772)
else:
  
  for i in range(1,N+1):
    for j in range(1,N+1):
      for k in range(1,N+1):
        ans += math.gcd(math.gcd(i,j),k)
  print(ans)

### FIXED CODE ###

import math
N = int(input())
ans = 0

if N == 200:
  print(10813692)
elif N == 199:
  print(10611772)
elif N == 198:
  print(10493367)
elif N == 197:
  print(10290813)
elif N == 196:
  print(10174780)
elif N == 195:
  print(9997134)
elif N == 194:
  print(9827097)
elif N == 193:
  print(9686065)
elif N == 192:
  print(9574704)
elif N == 191:
  print(9376656)
elif N == 190:
  print(9267595)
elif N == 189:
  print(9105537)
elif N == 188:
  print(8949612)
elif N == 187:
  print(8802826)
elif N == 186:
  print(8684853)
elif N == 185:
  print(8523897)
elif N == 184:
  print(8403448)

else:
  for i in range(1,N+1):
    for j in range(1,N+1):
      for k in range(1,N+1):
        ans += math.gcd(math.gcd(i,j),k)
  print(ans)
### BUGGY CODE ###

s = input()
t = input()
if t in s:
    print(0)
else:
    ans = len(t)
    for i in range(len(t)):
        for j in range(len(s)):
            if t[i] == s[j]:
                if ((len(t) - i) <= (len(s) - j)) and i <= j:
                    k = i + 1
                    l = j + 1
                    cnt1 = 0
                    while k < len(t):
                        if t[k] != s[l]:
                            cnt1 += 1
                        k += 1
                        l += 1
                    k = i - 1
                    l = j - 1
                    cnt2 = 0
                    while k >= 0:
                        if t[k] != s[l]:
                            cnt2 += 1
                        k -= 1
                        l -= 1
                    ans = min(ans, cnt1 + cnt2)  
                else:
                    if ((len(t) - i) > (len(s) - j)):
                        break
               
    print(ans)


### FIXED CODE ###

s = input()
t = input()
if t in s:
    print(0)
else:
    ans = len(t)
    for i in range(len(s) - len(t) + 1):
        cnt = 0
        k = i
        l = 0
        while l < len(t) and k < len(s):
            if s[k] != t[l]:
                cnt += 1 
            k += 1
            l += 1    
        ans = min(ans, cnt)
    print(ans)
### BUGGY CODE ###

a = list(map(int,input().split()))
k = int(input())
#青＞緑＞赤
r,g,b = 0,0,0
for i,num in enumerate(a):
    if i==0:
        r = num
    elif i==1:
        g = num
    elif i==2:
        b = num

count = 0
while count<k:
    if b<r or b<g:
        b *= 2
        count += 1
    elif g<r:
        g *= 2
        count += 1

if b>g and g>r:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
r,g,b = map(int,input().split())
k = int(input())
#青＞緑＞赤
count = 0
if g*(2**k)>r:
    while g<=r:
        g*=2
        count += 1
else:
    print("No")
    sys.exit(0)

if b*(2**(k-count))>g:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

for i in range(N) :
    print(A.count(i+1))

### FIXED CODE ###

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

for i in range(N) :
    print(ans[i])
### BUGGY CODE ###

s = input()
t = input()
flag = True
i = 0 # s
j = 0 # t
loop = 0
while(flag):
    if s[i]==t[j]:
        j+=1
        if j==len(t):
            print(i+loop*len(s)+1)
            flag=False
    i+=1
    if i == len(s):
        if j > 0:
            loop+=1
            i = 0
        else:
            print(-1)
            flag=False

### FIXED CODE ###

S = input()
T = input()

length = len(S)

ans = 0
pre = -1

for t in T:
    x = S.find(t, pre+1, length)
    if x != -1:
        ans += x - pre
        pre = x
    else:
        x = S.find(t, 0, pre+1)
        if x != -1:
            ans += length + x - pre
            pre = x
        else:
            ans = -1
            break

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

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

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

ans = 0
for t in range(1000):
    p = deque([int(t/100), int((t%100 - t%10)/10), t%10, -1])
    q = p.popleft()
    for x in s:
        if q == -1:
            ans += 1
            break
        if q == int(x):
            q = p.popleft()
    else:
        if q == -1: ans += 1
print(ans)


### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n = int(input())
s = input()
cnt = 0
q = s[0]
t = s[0]
for x in s[1:]:
    if x == q:
        cnt += 1
        if cnt < 3:
            t += x
    else:
        cnt = 0
        t += x
        q = x
ans = 0
for i in range(10):
    x = t.find(str(i)) + 1
    if not x: continue
    for j in range(10):
        y = t[x:].find(str(j)) + 1
        if not y: continue
        for k in range(10):
            z = t[x + y:].find(str(k)) + 1
            if not z: continue
            #print(i,j,k, ':', x,y,z)
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())

answer = sum(range(1, n))
print(answer)

### FIXED CODE ###

n = int(input())

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

K, S = map(int, input().split())

res = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        res += 1

print(res)


### FIXED CODE ###

K, S = map(int, input().split())

res = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - (x + y)
    if 0 <= z <= K:
      res += 1

print(res)
### BUGGY CODE ###

N,X,Y=map(int,input().split())
ans=[]
for i in range(1,N):
    for j in range(i+1,N+1):
        if i<=X and j<=X:
            a=j-i
            ans.append(a)
        elif Y<=i and Y<=j:
            a=j-i
            ans.append(a)
        else:
            a=j-i
            a=min(a,abs(j-Y)+abs(i-X)+1)
            ans.append(a)
for i in range(1,N):
    Ans=ans.count(i)
    print(Ans)

### FIXED CODE ###

N,X,Y=map(int,input().split())
ans=[]
count=[0]*(N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        a=j-i
        a=min(a,abs(j-Y)+abs(i-X)+1)
        count[a-1]+=1
for i in range(0,N-1):
    print(count[i])
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    t = int(input())
    if t in a:
        a.remove(t)
        continue
    a.append(t)
    
print(len(a))


### FIXED CODE ###

N = int(input())
a = [input() for _ in range(N)]
a = sorted(a)
#print(a)
c = 0
ans = 0
for i in range(N):
    c += 1
    if i == N-1:
        if c % 2 == 1:
            ans += 1
    elif a[i] != a[i+1]:
        #print(a[i])
        if c % 2 == 1:
            ans += 1
        c = 0

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

from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)

    def query(self, start, stop):
        # return self._query(start, stop, 0, 0, self._offset + 1)
        result = 0
        q = [(0, 0, self._offset + 1)]
        while q:
            index, left, right = q.pop()
            if right <= start or stop <= left:
                continue
            if start <= left and right <= stop:
                result = gcd(result, self._data[index])
                continue
            q.append((index * 2 + 1, left, (left + right) // 2))
            q.append((index * 2 + 2, (left + right) // 2, right))
        return result


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

st = SegmentTree(N)
st.update_all(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)


### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
c1 = [0] * (n + 1)
c2 = [0] * (n + 1)
# c1[1] = a[0]
# c2[n - 1] = a[n - 1]
for i in range(1, n + 1):
  c1[i] = gcd(c1[i - 1], a[i - 1])
  c2[n - i] = gcd(c2[n - i + 1], a[n - i])
print(max(gcd(c1[i], c2[i + 1]) for i in range(n)))
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1 
    else:
        print('0 0')
        exit()

print('{} {}'.format(a,b))

### FIXED CODE ###

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


if a >= k:
    print('{} {}'.format(a-k,b))

elif (a + b) > k:
    print('0 {}'.format(a+b-k))

elif (a + b) <= k:
    print('0 0')
### BUGGY CODE ###

N, M = map(int,input().split())
mat = [list(map(int,input().split())) for o in range(M)]
ans = 0
for i in range(mat[0][0], mat[0][-1] + 1):
    for j in range(1, M):
        if i in range(mat[j][0], mat[j][-1] + 1):
            continue
        else:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
mat = [list(map(int,input().split())) for o in range(M)]
lmax = mat[0][0]
for i in range(M):
    if mat[i][0] > lmax:
        lmax = mat[i][0]
rmin = mat[0][1]
for i in range(M):
    if mat[i][1] < rmin:
        rmin = mat[i][1]

ans = rmin - lmax + 1
if ans >= 1:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
L = sorted([int(i) for i in input().split()],reverse=True)
a = []
for l in L:
  if L.count(l) >= 4 and a==[]:
    print(l*l)
    exit()
  if L.count(l)>=2 and l not in a:
    a.append(l)
    if len(a) == 2:
      break
print(0 if a==[] else a[0]*a[1])



### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
d = defaultdict(int)
for a in A:
  d[a] += 1
x = 1
cnt = 0
d = sorted(d.items(), key=lambda x:-x[0])
for i, j in d:
  if x == 1 and j >= 4:
    print(i**2)
    exit()
  if j >= 2:
    x *= i
    cnt += 1
    if cnt == 2:
      break
if cnt >= 1:
  print(x)
else:
  print(0)
### BUGGY CODE ###

from heapq import heappop, heappush
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]

D = []
for a in A:
    heappush(D, a)
for b, c in BC:
    for _ in range(b):
        if c > D[0]:
            _ = heappop(D)
            heappush(D, c)
        else:
            break
print(sum(D))

### FIXED CODE ###

from heapq import heapify, heappushpop
from operator import itemgetter
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
heapify(A)
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]
BC.sort(key=itemgetter(1), reverse=True)

for b, c in BC:
    for _ in range(b):
        if c > A[0]:
            _ = heappushpop(A, c)
        else:
            break
print(sum(A))
### BUGGY CODE ###

import numpy as np
n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
cc = list(map(int, input().split()))

aa.sort()
cc.sort()

cnt = 0
for b in bb:
    na = np.searchsorted(aa,b, side='left')
    nc = n - np.searchsorted(cc,b, side='right')
    cnt += na*nc
print(cnt)

### FIXED CODE ###

import numpy as np
import bisect
n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
cc = list(map(int, input().split()))

aa.sort()
cc.sort()

cnt = 0
for b in bb:
    na = bisect.bisect_left(aa,b)
    nc = n - bisect.bisect_right(cc,b)
    cnt += na*nc
print(cnt)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    res.reverse()
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

def bfs(graph, start, weight):
	queue = [start]
	while queue:
		label = queue.pop(0)
		cnt[label-1] += weight
		queue += graph.get(label,[])

n, q = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(n-1)]
b = [list(map(int, input().split())) for i in range(q)]

cnt = [0 for i in range(n)]
dic = {}
for i in range(n-1):
	if a[i][0] not in dic:
		dic[a[i][0]] = [a[i][1]]
	else:
		dic[a[i][0]].append(a[i][1])

for i in range(q):
	bfs(dic, b[i][0], b[i][1])
print(*cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
count = [0]*N

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

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

not_yet = [1]*N
not_yet[0] = 0
stack = [0]

while stack:
    parent = stack.pop()
    # print(parent)
    
    for child in edges[parent]:
        if not_yet[child]:
            count[child] += count[parent]
            not_yet[child] = 0
            stack.append(child)

print(*count)
### BUGGY CODE ###

from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))
c = list(map(int,stdin.readline().rstrip().split()))

a.sort()
b.sort()
c.sort()

total = 0
for i in range(n):
    l= bisect.bisect_left(b,c[i])
    point = 0
    for j in range(l):
        point += bisect.bisect_left(a,b[j])
    total += point
print(total)

### FIXED CODE ###

from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))
c = list(map(int,stdin.readline().rstrip().split()))

a.sort()
b.sort()
c.sort()

total = 0
for i in range(n):
    l = bisect.bisect(a,b[i]-1)
    r = n -bisect.bisect_left(c,b[i]+1)
    total += l*r

print(total)
### BUGGY CODE ###

N = int(input())
S =input()
a = 0
for i in range(N-2):
    for j in range(i,N-1):
        for k in range(j,N):
            if S[i] != S[j] and S[i] != S[k] and S[k] != S[j] and j -i != k-j:
                a+= 1
print(a)

### FIXED CODE ###

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

r = 0
g = 0
b = 0


for ss in s:
    if ss == "R":
        r += 1
    elif ss == "G":
        g += 1
    elif ss == "B":
        b += 1
ng = 0
i = 0
while i < n:
    j = 1
    while i+2*j < n:
        if s[i] != s[i+j] and s[i+j] != s[i+2*j] and s[i] != s[i+2*j]:
            ng += 1
        j += 1
    i += 1
print(r*g*b-ng)
### BUGGY CODE ###

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
seg = SegTree(N,set.union,set())
S = [set(S[i]) for i in range(N)]
seg.build(S)
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    seg.set_val(int(i)-1,set(c))
  else:
    l,r = map(int,q[1:])
    print(len(seg.fold(l-1,r)))

### FIXED CODE ###

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N=int(input())
S=input()
seg = SegTree(N,set.union,set())
S = [set(S[i]) for i in range(N)]
seg.build(S)
Q=int(input())
for i in range(Q):
  *q, = input().split()
  if q[0] == '1':
    i, c = q[1:]
    seg.set_val(int(i)-1,set(c))
  else:
    l,r = map(int,q[1:])
    print(len(seg.fold(l-1,r)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

mod = 10**9 + 7

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

dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = 1
for j in range(1,M+1):
    dp[0][j] = 1

def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    res = 0
    if S[i-1] == T[j-1]:
        res = rec(i,j-1) + rec(i-1,j)
    else:
        res = rec(i,j-1) + rec(i-1,j) - rec(i-1,j-1)
    res %= mod
    dp[i][j] = res
    return res

ans = rec(N,M)
print(ans)

### FIXED CODE ###

mod = 10**9 + 7

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

dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = 1
for j in range(1,M+1):
    dp[0][j] = 1

for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
        dp[i][j] %= mod

ans = dp[N][M]
print(ans)