AtCoder Beginner Contest 130 - Common Subsequence

You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).
In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?
Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.
For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.
Since the answer can be tremendous, print the number modulo 10^9+7.

-----Constraints-----
 - 1 \leq N, M \leq 2 \times 10^3
 - The length of S is N.
 - The length of T is M.     
 - 1 \leq S_i, T_i \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
S_1 S_2 ... S_{N-1} S_{N}
T_1 T_2 ... T_{M-1} T_{M}

-----Output-----
Print the number of pairs of a subsequence of S and a subsequence of T such that the subsequences are the same in content, modulo 10^9+7.

-----Sample Input-----
2 2
1 3
3 1

-----Sample Output-----
3

S has four subsequences: (), (1), (3), (1, 3).
T has four subsequences: (), (3), (1), (3, 1).
There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
def main():
	mod = 10 ** 9 + 7
	(N, M) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	u = [1] * (N + 1)
	v = [1] * (N + 1)
	for t in T:
		for (i, s) in enumerate(S, 1):
			if s == t:
				v[i] = v[i - 1] + u[i]
			else:
				v[i] = v[i - 1] + u[i] - u[i - 1]
		(u, v) = (v, u)
	return u[-1] % mod
print(main())


(n, m) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * m
for s in S:
	k = 0
	d = [0] * (m + 1)
	for i in range(m):
		if T[i] == s:
			k += dp[i - 1] + 1
		d[i] = (dp[i] + k) % mod
	dp = d
print(dp[-2] + 1)


MOD = 10 ** 9 + 7
INF = float('inf')
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[-INF] * (M + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(N + 1):
	dp[i][0] = 1
for j in range(M + 1):
	dp[0][j] = 1
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MOD
		else:
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + MOD) % MOD
print(dp[N][M])


(n, m) = map(int, input().split())
s = input().split()
t = input().split()
dp = [[1] * (m + 1)] + [[1] + [0] * m for _ in range(n)]
for i in range(n):
	for j in range(m):
		dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j] * (s[i] != t[j])) % (10 ** 9 + 7)
print(dp[-1][-1])


import numpy as np
(N, M) = map(int, input().split())
MOD = 1000000000.0 + 7
S = np.array(input().split())
T = np.array(input().split())
dp = np.zeros((N + 1, M + 1))
dp[0] = 1
for n in range(1, N + 1):
	same = T == S[n - 1]
	dp[n, 1:][same] = dp[n - 1, :-1][same]
	dp[n] = (dp[n].cumsum() + dp[n - 1]) % MOD
print(int(dp[N, M]))


import numpy as np
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
(N, M) = list(map(int, input().split()))
S = np.array(input().split(), dtype=np.int32)
T = np.array(input().split(), dtype=np.int32)
dp = np.zeros((N + 1, M + 1), dtype=np.int64)
dp[0] = 1
for n in range(1, N + 1):
	same = T == S[n - 1]
	dp[n, 1:][same] = dp[n - 1, :-1][same]
	dp[n] = (dp[n].cumsum() + dp[n - 1]) % MOD
answer = dp[N, M]
print(answer)


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[1] + [0] * len(T) for i in range(len(S) + 1)]
dp[0] = [1] * (len(T) + 1)
dp_sum = [[1] + [0] * len(T) for i in range(len(S) + 1)]
dp_sum[0] = [1] * (len(T) + 1)
for i in range(len(S)):
	for j in range(len(T)):
		if S[i] == T[j]:
			dp[i + 1][j + 1] = dp_sum[i][j]
		dp_sum[i + 1][j + 1] = (dp[i + 1][j + 1] + dp_sum[i + 1][j] + dp_sum[i][j + 1] - dp_sum[i][j]) % (10 ** 9 + 7)
print(dp_sum[-1][-1])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
a = [1] * (m + 1)
for i in range(n):
	b = a[:]
	k = 0
	for j in range(m):
		b[j] = (k + b[j]) % (10 ** 9 + 7)
		if s[i] == t[j]:
			k = (k + a[j]) % (10 ** 9 + 7)
	b[-1] = (k + b[-1]) % (10 ** 9 + 7)
	a = b[:]
print(a[-1] % (10 ** 9 + 7))


import numpy as np
(N, M) = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype=np.int32)
dp = np.ones(M + 1, dtype=np.int64)
for s in S:
	dp[1:] = (np.where(T == int(s), dp[:-1], 0).cumsum() + dp[1:]) % (10 ** 9 + 7)
print(dp[M])


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m + 3) for _ in range(n + 3)]
for i in range(n + 3):
	dp[i][0] = 1
for i in range(m + 3):
	dp[0][i] = 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 - 1][j] + dp[i][j - 1]
		else:
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		dp[i][j] %= MOD
print(dp[n][m] % MOD)


def solve():
	(N, M) = map(int, input().split())
	S = map(int, input().split())
	(*T,) = map(int, input().split())
	dp = [1] * (M + 1)
	for s in S:
		is_s = s.__eq__
		dp_ = dp[:]
		acc = 0
		for (i, t) in enumerate(T):
			if is_s(t):
				acc += dp_[i]
			dp[i + 1] = dp_[i + 1] + acc
	res = dp[-1] % (10 ** 9 + 7)
	return str(res)

def __starting_point():
	print(solve())
__starting_point()


(n, m) = map(int, input().split())
s = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		x = 0
		if s[i] == t[j]:
			x = dp[i][j] + 1
		dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + x) % mod
print((dp[n][m] + 1) % mod)


def f(N, M, S, T):
	W = [1] * (N + 1)
	for (i, t) in enumerate(T):
		W2 = W[:]
		k = 0
		for (j, s) in enumerate(S):
			if t == s:
				k += W[j]
			x = (W2[j + 1] + k) % 1000000007
			W2[j + 1] = x
		W = W2
	return W[-1]

def main():
	(N, M) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	print(f(N, M, S, T))
main()


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]
for (i, s) in enumerate(S, start=1):
	for (j, t) in enumerate(T, start=1):
		if s == t:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % MOD
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD
print((dp[N][M] + 1) % MOD)


from numpy import *
(N, M, *U) = map(int, open(0).read().split())
T = array(U[N:])
p = ones(M + 1, dtype='i8')
for s in U[:N]:
	p[1:] = ((p[:-1] * (s == T)).cumsum() + p[1:]) % (10 ** 9 + 7)
print(p[-1])


(N, M) = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10 ** 9 + 7
x = 2160
dp = [[0] * x for i in range(x)]
for i in range(N):
	for j in range(M):
		if Ss[i] == Ts[j]:
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1) % mod
		else:
			dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) % mod
print((dp[N][M] + 1) % mod)


MOD = 10 ** 9 + 7
(n, m) = (int(num) for num in input().split())
s = [int(num) for num in input().split()]
t = [int(num) for num in input().split()]
dp = [[1] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		if s[i - 1] == t[j - 1]:
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] = dp[i][j] % MOD
print(dp[n][m])


import sys
input = sys.stdin.readline
MOD = int(1000000000.0 + 7)

def f(N, M, s, t):
	cums = [[0] * (M + 1) for _ in range(N + 1)]
	for i in range(N):
		cumsi = cums[i]
		cumsi1 = cums[i + 1]
		for j in range(M):
			num = 0
			if s[i] == t[j]:
				num = cumsi[j] + 1
			cumsi1[j + 1] = (cumsi1[j] + cumsi[j + 1] - cumsi[j] + num) % MOD
	return (cums[N][M] + 1) % MOD
(n, m) = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))


mod = 1000000007
(n, m) = map(int, input().split())
S = tuple(map(int, input().split()))
T = tuple(map(int, input().split()))
DP = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
	DP[i][0] = 1
for i in range(m + 1):
	DP[0][i] = 1
for (i, s) in enumerate(S):
	for (j, t) in enumerate(T):
		if s == t:
			DP[i + 1][j + 1] = DP[i][j + 1] + DP[i + 1][j]
		else:
			DP[i + 1][j + 1] = DP[i][j + 1] + DP[i + 1][j] - DP[i][j]
		DP[i + 1][j + 1] %= mod
print(DP[-1][-1])


from collections import defaultdict
(N, M) = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
mod = 10 ** 9 + 7
sum_dp = []
for i in range(N + 1):
	sum_dp.append([0] * (M + 1))
temp = 0
for i in range(1, N + 1):
	for j in range(1, M + 1):
		temp = 0
		if S[i] == T[j]:
			temp = sum_dp[i - 1][j - 1] + 1
		sum_dp[i][j] = (sum_dp[i - 1][j] + sum_dp[i][j - 1] - sum_dp[i - 1][j - 1] + temp) % mod
print(sum_dp[N][M] + 1)


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [0] * n
ndp = [0] * n
for tj in t:
	for i in range(n):
		ndp[i] = 0
	acc = 0
	for (i, si) in enumerate(s):
		if si == tj:
			ndp[i] = (dp[i] + acc + 1) % MOD
		else:
			ndp[i] = dp[i]
		acc = (acc + dp[i]) % MOD
	(dp, ndp) = (ndp, dp)
print((sum(dp) + 1) % MOD)


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)


(N, M) = map(int, input().split())
S = [int(i) for i in input().split()] + ['g']
T = [int(i) for i in input().split()] + ['a']
MOD = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N + 1):
	dp[i][0] = 1
for i in range(M + 1):
	dp[0][i] = 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 - 1][j] + dp[i][j - 1]) % MOD
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD
print(dp[N][M])


(n, m) = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(m):
		d[i + 1][j + 1] = (d[i][j + 1] + d[i + 1][j] - (ss[i] != ts[j]) * d[i][j]) % (10 ** 9 + 7)
print(d[n][m])


import numpy as np
(N, M) = list(map(int, input().split()))
S = tuple(map(int, input().split()))
T = np.array(input().split(), np.int64)
mod = 10 ** 9 + 7
dp = np.ones(M + 1, np.int64)
for i in S:
	tmp = T == i
	dp[1:] = (np.cumsum(tmp * dp[:-1]) + dp[1:]) % mod
print(dp[-1])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
	dp[i][0] = 1
for j in range(m + 1):
	dp[0][j] = 1
for (i, es) in enumerate(s, 1):
	for (j, et) in enumerate(t, 1):
		dp[i][j] += dp[i - 1][j]
		dp[i][j] += dp[i][j - 1]
		dp[i][j] -= dp[i - 1][j - 1]
		if es == et:
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] %= mod
ans = dp[n][m]
print(ans)


(n, m) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [1] * (m + 1)
for i in range(n):
	tmp = dp[:]
	for j in range(m):
		if S[i] == T[j]:
			dp[j + 1] = (tmp[j + 1] + dp[j]) % mod
		else:
			dp[j + 1] = (tmp[j + 1] + dp[j] - tmp[j]) % mod
print(dp[-1])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 1000000007
dp = [[0 for j in range(M + 1)] for i in range(N + 1)]
Sum = [[0 for j in range(M + 1)] for i in range(N + 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] = Sum[i - 1][j - 1]
			dp[i][j] += 1
		Sum[i][j] = (Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + dp[i][j]) % mod
print(Sum[N][M] + 1)


MOD = 1000000007
(N, M) = map(int, input().split())
S = [int(s) for s in input().split()]
T = [int(s) for s in input().split()]
m = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			m[i][j] = m[i - 1][j] + m[i][j - 1] + 1
			m[i][j] %= MOD
		else:
			m[i][j] = m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1]
			m[i][j] %= MOD
print((m[N][M] + 1) % MOD)


(N, M) = map(int, input().split())
S = tuple(map(int, input().split()))
T = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[1] * (M + 1) for _ in range(N + 1)]
for i in range(N):
	for j in range(M):
		dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
		if S[i] != T[j]:
			dp[i + 1][j + 1] -= dp[i][j]
		dp[i + 1][j + 1] %= MOD
print(dp[N][M])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [[0 for j in range(M + 1)] for i in range(N + 1)]
for i in range(N + 1):
	for j in range(M + 1):
		if i == 0 or j == 0:
			a[i][j] = 1
		else:
			a[i][j] = a[i - 1][j] + a[i][j - 1] - (a[i - 1][j - 1] if S[i - 1] != T[j - 1] else 0)
			a[i][j] %= MOD
print(a[N][M])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0] * (M + 1) for i in range(N + 1)]
mod = 10 ** 9 + 7
for n in range(1, N + 1):
	for m in range(1, M + 1):
		x = 1 if S[n - 1] == T[m - 1] else -dp[n - 1][m - 1]
		y = dp[n - 1][m] + dp[n][m - 1] + x
		dp[n][m] = y if y < mod else y - mod
print((dp[-1][-1] + 1) % mod)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, M) = list(map(int, readline().split()))
	S = list(map(int, readline().split()))
	T = list(map(int, readline().split()))
	dp = [1] * (M + 1)
	for i in range(N):
		dp_prev = dp[:]
		for j in range(M):
			if S[i] == T[j]:
				dp[j + 1] = (dp_prev[j + 1] + dp[j]) % MOD
			else:
				dp[j + 1] = (dp_prev[j + 1] + dp[j] - dp_prev[j]) % MOD
	print(dp[M])
	return

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M + 1)
dpleft = [0] * M
MOD = 10 ** 9 + 7
ndp = [1] * (M + 1)
for n in range(N):
	for m in range(M):
		if S[n] == T[m]:
			ndp[m + 1] = (ndp[m] + dp[m + 1]) % MOD
			dpleft[m] = dp[m + 1]
		else:
			ndp[m + 1] = (ndp[m] + dpleft[m]) % MOD
		dp[m] = ndp[m]
	dp[-1] = ndp[-1]
print(dp[-1])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m + 2) for _ in range(n + 2)]
mod = 1000000007
for i in range(n + 1):
	dp[i][0] = 1
for i in range(m + 1):
	dp[0][i] = 1
for i in range(1, n + 1):
	for j in range(1, m + 1):
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod
		if s[i - 1] == t[j - 1]:
			dp[i][j] += dp[i - 1][j - 1]
			dp[i][j] %= mod
print(dp[n][m])


(n, m) = map(int, input().split())
s_list = [0] + list(map(int, input().split()))
t_list = [0] + list(map(int, input().split()))
dp = []
for i in range(n + 1):
	sub_list = [0] * (m + 1)
	dp.append(sub_list)
for j in range(m + 1):
	dp[0][j] = 1
for i in range(n + 1):
	dp[i][0] = 1
Mod = 10 ** 9 + 7
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s_list[i] == t_list[j]:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % Mod
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % Mod
print(dp[n][m])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[1] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod
		if S[i - 1] == T[j - 1]:
			dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod
print(dp[N][M])


(n, m) = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
a = [1] * (m + 1)
for b in s:
	d = a[:]
	k = 0
	for (j, c) in enumerate(t):
		d[j] = (k + d[j]) % 1000000007
		if b == c:
			k = (k + a[j]) % 1000000007
	d[-1] = (k + d[-1]) % 1000000007
	a = d[:]
print(a[-1])


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [0] * n
for tj in t:
	acc = 0
	for (i, si) in enumerate(s):
		acc = (acc + dp[i]) % 1000000007
		if si == tj:
			dp[i] = (acc + 1) % 1000000007
ans = 1
for x in dp:
	ans = (ans + x) % MOD
print(ans)


from itertools import accumulate
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
for (i, t) in enumerate(T, 1):
	dp2 = dp[:]
	for i in range(1, N + 1):
		dp2[i] = (dp2[i - 1] + dp2[i]) % mod
	for (j, s) in enumerate(S, 1):
		if s == t:
			dp[j] += dp2[j - 1]
ans = 0
for d in dp:
	ans = (ans + d) % mod
print(ans)


inpl = lambda : list(map(int, input().split()))
MOD = 10 ** 9 + 7
(N, M) = inpl()
S = inpl()
T = inpl()
total = [0] * (N + 1) * (M + 1)
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			n = total[(M + 1) * i + j] + 1
		else:
			n = 0
		total[(M + 1) * (i + 1) + (j + 1)] = (n + total[(M + 1) * i + (j + 1)] + total[(M + 1) * (i + 1) + j] - total[(M + 1) * i + j]) % MOD
print((total[-1] + 1) % MOD)


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0] * 2010 for _ in range(2010)]
dp[0][0] = 1
for i in range(N + 1):
	for j in range(M + 1):
		if i > 0:
			dp[i][j] += dp[i - 1][j]
		if j > 0:
			dp[i][j] += dp[i][j - 1]
		if i > 0 and j > 0:
			dp[i][j] -= dp[i - 1][j - 1]
			if S[i - 1] == T[j - 1]:
				dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] = (dp[i][j] + MOD) % MOD
print(dp[N][M])


from copy import deepcopy
mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = [1 for i in range(m + 1)]
for i in s:
	ans2 = deepcopy(ans)
	cnt = 0
	for j in range(m):
		ans2[j] = (cnt + ans2[j]) % mod
		if i == t[j]:
			cnt = (cnt + ans[j]) % mod
	ans2[-1] = (cnt + ans2[-1]) % mod
	ans = deepcopy(ans2)
print(ans[-1])


(N, M) = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]
dp = [[1] * (M + 1) for _ in range(N + 1)]
mod = 1000000007
for n in range(N):
	for m in range(M):
		if S_arr[n] == T_arr[m]:
			dp[n + 1][m + 1] = (dp[n + 1][m] + dp[n][m + 1]) % mod
		else:
			dp[n + 1][m + 1] = (dp[n + 1][m] + dp[n][m + 1] - dp[n][m]) % mod
print(dp[N][M])


(N, M) = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
DP = [[0] * (N + 1) for i in range(M + 1)]
for i in range(N + 1):
	DP[0][i] = 1
for i in range(M + 1):
	DP[i][0] = 1
mod = 10 ** 9 + 7
for i in range(M):
	for j in range(N):
		if T[i] == S[j]:
			DP[i + 1][j + 1] = (DP[i + 1][j] + DP[i][j + 1]) % mod
		else:
			DP[i + 1][j + 1] = (DP[i + 1][j] + DP[i][j + 1] - DP[i][j]) % mod
print(DP[M][N])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 1000000007
dp = [1] + [1] * m
for i in range(n):
	newdp = [1] + [0] * m
	for j in range(m):
		if s[i] == t[j]:
			newdp[j + 1] = (newdp[j] + dp[j + 1]) % mod
		else:
			newdp[j + 1] = (newdp[j] + dp[j + 1] - dp[j] + mod) % mod
	dp = newdp
print(dp[-1])


def f(n, m):
	s = list(map(int, input().split()))
	t = list(map(int, input().split()))
	dpi = [1] * (m + 1)
	for (i, sk) in enumerate(s):
		dpi1 = dpi[:]
		cs = 0
		for (j, tk) in enumerate(t):
			if sk == tk:
				cs = (cs + dpi[j]) % md
			dpi1[j + 1] = (dpi1[j + 1] + cs) % md
		dpi = dpi1
	print(dpi1[-1])
md = 10 ** 9 + 7
(n, m) = map(int, input().split())
f(n, m)


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
S.append(0)
T.append(0)
MOD = 1000000007
dp0 = [[0 for _ in range(2005)] for _ in range(2005)]
dp1 = [[0 for _ in range(2005)] for _ in range(2005)]
dp0[0][0] = 1
for i in range(N + 1):
	for j in range(M + 1):
		dp0[i + 1][j] += dp0[i][j] % MOD
		dp1[i][j] += dp0[i][j] % MOD
		dp1[i][j + 1] += dp1[i][j] % MOD
		if S[i] == T[j]:
			dp0[i + 1][j + 1] += dp1[i][j] % MOD
ans = dp1[N][M]
print(ans % MOD)


nl = lambda : list(map(int, input().split()))
sl = lambda : input().split()
n = lambda : int(input())
s = lambda : input()
(N, M) = nl()
S = nl()
T = nl()
dp = [0] * (M + 1)
for (i, s) in enumerate(S):
	dp2 = dp[:]
	for (j, t) in enumerate(T):
		dp2[j + 1] += dp2[j] - dp[j]
		if s == t:
			dp2[j + 1] += dp[j] + 1
	dp = dp2
print((dp[M] + 1) % 1000000007)


from functools import reduce
NNN = 10 ** 9 + 7

def main():
	(N, M) = [int(a) for a in input().split()]
	S = [int(a) for a in input().split()]
	T = [int(a) for a in input().split()]
	table = [0] * M
	for si in reversed(S):
		c = 0
		for i in reversed(list(range(M))):
			prev_score = table[i]
			if T[i] == si:
				table[i] = (table[i] + c + 1) % NNN
			c = (c + prev_score) % NNN
	s = 1
	for a in table:
		s = (s + a) % NNN
	print(s)

def __starting_point():
	main()
__starting_point()


def inpl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
(N, M) = inpl()
S = [0] + inpl()
T = [0] + inpl()
DP = [[1] * (N + 1) for _ in range(M + 1)]
for i in range(1, M + 1):
	for j in range(1, N + 1):
		if S[j] == T[i]:
			DP[i][j] = (DP[i][j - 1] + DP[i - 1][j]) % MOD
		else:
			DP[i][j] = (DP[i][j - 1] + DP[i - 1][j] - DP[i - 1][j - 1]) % MOD
print(DP[-1][-1])


(h, w) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 10 ** 9 + 7
now = [1 for _ in range(w + 1)]
for i in range(h):
	last = now
	now = [1]
	for j in range(w):
		if a[i] == b[j]:
			now.append((last[j + 1] + now[-1]) % mod)
		else:
			now.append((last[j + 1] + now[-1] - last[j]) % mod)
print(now[-1])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
A = []
B = []
mod = 10 ** 9 + 7
for i in range(N):
	if S[i] in T:
		A.append(S[i])
for i in range(M):
	if T[i] in S:
		B.append(T[i])
l1 = [1] * (N + 1)
for (i, t) in enumerate(T):
	l2 = l1[:]
	k = 0
	for (j, s) in enumerate(S):
		if t == s:
			k += l1[j]
		l2[j + 1] = (l1[j + 1] + k) % mod
	l1 = l2
print(l1[-1])


(N, M) = map(int, input().split())
mod = 10 ** 9 + 7
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
dp = [[0] * (M + 1) for i in range(N + 1)]
dp[0][0] = 1
Sum = [[0] * (M + 1) for i in range(N + 1)]
for i in range(N + 1):
	Sum[i][0] = 1
for j in range(M + 1):
	Sum[0][j] = 1
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			dp[i + 1][j + 1] = Sum[i][j]
		Sum[i + 1][j + 1] = (dp[i + 1][j + 1] + Sum[i][j + 1] + Sum[i + 1][j] - Sum[i][j]) % mod
print(Sum[N][M])


from collections import defaultdict
import bisect
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = max(n, m)
if n > m:
	t.extend((0,) * (n - m))
else:
	s.extend((0,) * (m - n))
dp = [[1 for i in range(p + 1)] for j in range(p + 1)]
for i in range(1, p + 1):
	for j in range(1, p + 1):
		x = s[i - 1]
		y = t[j - 1]
		if x == y:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
		else:
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % mod
print(dp[-1][-1])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
C = [1] * (N + 1)
for t in T:
	d = 0
	for (i, s) in enumerate(S):
		d_ = C[i]
		if t == s:
			ans = (ans + d_) % mod
		C[i] += d
		C[i] %= mod
		if t == s:
			d += d_
			d %= mod
print(ans + 1)


mod = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for s in range(len(S) + 1):
	for t in range(len(T) + 1):
		if s == 0 or t == 0:
			dp[s][t] = 1
for s in range(len(S)):
	for t in range(len(T)):
		if S[s] == T[t]:
			dp[s + 1][t + 1] = (dp[s + 1][t] + dp[s][t + 1]) % mod
		else:
			dp[s + 1][t + 1] = (dp[s + 1][t] + dp[s][t + 1] - dp[s][t]) % mod
print(dp[len(S)][len(T)])


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
dp = [[1] * (M + 1) for _ in range(N + 1)]
for (i, S) in enumerate(Ss, 1):
	for (j, T) in enumerate(Ts, 1):
		dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		if S != T:
			dp[i][j] -= dp[i - 1][j - 1]
		dp[i][j] %= MOD
print(dp[-1][-1])


(N, M) = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0] * M for _ in range(N)]
dp[0][0] = 1 + int(S[0] == T[0])
for i in range(1, N):
	dp[i][0] = dp[i - 1][0] + int(S[i] == T[0])
for j in range(1, M):
	dp[0][j] = dp[0][j - 1] + int(T[j] == S[0])
for n in range(1, N):
	for m in range(1, M):
		dp[n][m] = (dp[n - 1][m] + dp[n][m - 1] - dp[n - 1][m - 1] + dp[n - 1][m - 1] * int(S[n] == T[m])) % MOD
print(dp[N - 1][M - 1])


mod = 10 ** 9 + 7
from bisect import bisect
from collections import defaultdict
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0] * (M + 1) for _ in range(N + 1)]
for n in range(N):
	for m in range(M):
		dp[n][m] = dp[n - 1][m] + dp[n][m - 1] - dp[n - 1][m - 1]
		if S[n] == T[m]:
			dp[n][m] += dp[n - 1][m - 1] + 1
		dp[n][m] %= mod
print(dp[N - 1][M - 1] + 1)


def main():
	e = enumerate
	(n, m, *u) = map(int, open(0).read().split())
	dp = [[1] * (m + 1) for _ in range(n + 1)]
	dpi = dp[0]
	for (i, s) in e(u[:n]):
		dpi1 = dp[i + 1]
		for (j, t) in e(u[n:]):
			dpi1[j + 1] = (dpi[j + 1] + dpi1[j] - dpi[j] * (s != t)) % (10 ** 9 + 7)
		dpi = dpi1
	print(dpi[m])
main()


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 i in range(N + 1)]
S_index = [[] for i in range(10 ** 5 + 1)]
for i in range(N):
	S_index[S[i]].append(i)
	if len(S_index[S[i]]) >= 2:
		ikkomae = S_index[S[i]][-2]
		for j in range(M + 1):
			dp[i - 1][j] = (dp[i - 1][j] + dp[ikkomae - 1][j]) % MOD
	for j in range(M):
		dp[i][j] = dp[i][j - 1]
		if len(S_index[T[j]]) >= 1:
			dp[i][j] = (dp[i][j] + dp[S_index[T[j]][-1] - 1][j - 1]) % MOD
print(dp[N - 1][M - 1])


def solve():
	MOD = 10 ** 9 + 7
	(N, M) = map(int, input().split())
	Ss = list(map(int, input().split()))
	Ts = list(map(int, input().split()))
	dp = [1] * (M + 1)
	for (i, S) in enumerate(Ss, 1):
		dp2 = [1] * (M + 1)
		for (j, T) in enumerate(Ts, 1):
			dp2[j] = dp[j] + dp2[j - 1]
			if S != T:
				dp2[j] -= dp[j - 1]
			dp2[j] %= MOD
		dp = dp2
	print(dp[-1])
solve()


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if a[i - 1] == b[j - 1]:
			dp[i][j] = (1 + dp[i - 1][j] + dp[i][j - 1]) % MOD
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD
print((dp[n][m] + 1) % MOD)


import os
import sys
import numpy as np
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
(N, M) = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = np.array([-1] + S)
T = np.array([-1] + T)
cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
	cumsum[1:] += ((T == S[i])[1:] * cumsum[:-1] % MOD).cumsum()
	cumsum %= MOD
print(cumsum[-1])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
assert len(S) == N
assert len(T) == M
modulo = 10 ** 9 + 7
tab = [[s == t for s in S] for t in T]
for t in tab:
	t.append(1)
tab.append([1] * (len(S) + 1))
for j in range(M - 1, -1, -1):
	for i in range(N - 1, -1, -1):
		v = tab[j + 1][i] + tab[j][i + 1]
		v -= 0 if tab[j][i] else tab[j + 1][i + 1]
		tab[j][i] = v % modulo
print(tab[0][0])


M = int(1000000000.0 + 7)

def main():
	input()
	s = list(map(int, input().split()))
	t = list(map(int, input().split()))
	z = [0] * len(t)
	for v in s:
		c = 0
		for (i, w) in enumerate(t):
			y = z[i]
			if v == w:
				z[i] = (z[i] + c + 1) % M
			c = (c + y) % M
	y = 0
	for v in z:
		y = (y + v) % M
	y = (y + 1) % M
	print(y)
main()


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = [0] * m
for u in s:
	h = [0] * m
	if u == t[0]:
		h[0] = 1
	for i in range(1, m):
		if t[i] == u:
			h[i] += ans[i - 1] + 1
		h[i] += h[i - 1]
	for i in range(m):
		ans[i] = (ans[i] + h[i]) % mod
print((ans[-1] + 1) % mod)


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
sum = [[0 for i in range(m + 1)] for i in range(n + 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] = (sum[i - 1][j - 1] + 1) % mod
		else:
			dp[i][j] = 0
		sum[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + dp[i][j]) % mod
print((sum[-1][-1] + 1) % mod)


(N, M) = map(int, input().split())
(*S,) = map(int, input().split())
(*T,) = map(int, input().split())
data = [0] * (M + 2)

def get(k):
	s = 0
	while k:
		s += data[k]
		k -= k & -k
	return s % MOD

def add(k, x):
	while k <= M:
		data[k] = (data[k] + x) % MOD
		k += k & -k
MOD = 10 ** 9 + 7
s = 0
rM = range(M - 1, -1, -1)
for i in range(N):
	si = S[i]
	for j in rM:
		if si == T[j]:
			v = get(j + 1) + 1
			add(j + 2, v)
			s += v
print((s + 1) % MOD)


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))
P = 10 ** 9 + 7
dp = [[0] * (M + 1) for i in range(N + 1)]
for x in range(1, N + 1):
	for y in range(1, M + 1):
		dp[x][y] = dp[x][y - 1] + dp[x - 1][y] - dp[x - 1][y - 1]
		if S[x - 1] == T[y - 1]:
			dp[x][y] += dp[x - 1][y - 1] + 1
		dp[x][y] = dp[x][y] % P
ans = dp[N][M] + 1
print(ans % P)


import itertools
(N, M) = [int(_) for _ in input().split()]
S = [int(_) for _ in input().split()]
T = [int(_) for _ in input().split()]
mod = 10 ** 9 + 7
dp = [[1] * (M + 1)] + [[1] + [0] * M for _ in range(N)]
for (n, m) in itertools.product(range(N), range(M)):
	dp[n + 1][m + 1] = dp[n][m + 1] + dp[n + 1][m] - dp[n][m]
	if S[n] == T[m]:
		dp[n + 1][m + 1] += dp[n][m]
	dp[n + 1][m + 1] %= mod
print(dp[-1][-1])


MOD = 10 ** 9 + 7
(n, m) = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for (i, tt) in enumerate(t):
	val = 0
	for (j, ss) in enumerate(s):
		if ss == tt:
			val += dp[i][j] + 1
			val %= MOD
		dp[i + 1][j + 1] += dp[i][j + 1] + val
		dp[i + 1][j + 1] %= MOD
print((dp[m][n] + 1) % MOD)


import numpy as np
MOD = 10 ** 9 + 7
(N, M) = list(map(int, input().split()))
s = np.array(input().split(), dtype=np.int32)
t = np.array(input().split(), dtype=np.int32)
dp = np.zeros((N + 1, M + 1), dtype=np.int64)
dp[0] = 1
for i in range(N):
	same = s[i] == t
	dp[i + 1, 1:][same] = dp[i, :-1][same]
	dp[i + 1] = (dp[i + 1].cumsum() + dp[i]) % MOD
print(dp[-1, -1])


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
[n, m] = i2()
s = i2()
t = i2()
x = 10 ** 9 + 7
cs = [[0 for i in range(2 * 10 ** 3)] for j in range(2 * 10 ** 3)]
y = 0
for i in range(n):
	if s[i] == t[0]:
		y += 1
	cs[i][0] = y + 0
y = 0
for i in range(m):
	if s[0] == t[i]:
		y += 1
	cs[0][i] = y + 0
for i in range(1, n):
	for j in range(1, m):
		if s[i] == t[j]:
			cs[i][j] = (cs[i - 1][j] + cs[i][j - 1] + 1) % x
		else:
			cs[i][j] = (cs[i - 1][j] + cs[i][j - 1] - cs[i - 1][j - 1]) % x
print((cs[n - 1][m - 1] + 1) % x)


MOD = 10 ** 9 + 7

def main(S, T):
	l = len(T) + 1
	dp = [0] * l
	for (i, s) in enumerate(S):
		tmp = [0] * l
		for (j, t) in enumerate(T):
			v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
			tmp[j + 1] = v % MOD
		dp = tmp
	return dp[-1] + 1

def __starting_point():
	if True:
		(_, _) = map(int, input().strip().split())
		S = input().strip().split()
		T = input().strip().split()
	else:
		S = range(1000)
		T = range(1000)
	print(main(S, T))
__starting_point()


(N, M) = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
	for j in range(1, nt + 1):
		if S[i - 1] == T[j - 1]:
			dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % MOD
		else:
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % MOD
print((dp[ns][nt] + 1) % MOD)


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[1] * (n + 1)] + [[1] + [0] * n for _ in range(m)]
arr_s = [0] + list(map(int, input().split()))
arr_t = [0] + list(map(int, input().split()))
for r in range(1, m + 1):
	for c in range(1, n + 1):
		if arr_s[c] == arr_t[r]:
			dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
		else:
			dp[r][c] = dp[r - 1][c] + dp[r][c - 1] - dp[r - 1][c - 1]
		dp[r][c] %= mod
print(dp[m][n])


def solve():
	(N, M) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	MOD = 10 ** 9 + 7
	dp = [[1] * (M + 1) for _ in range(N + 1)]
	for i in range(N):
		for j in range(M):
			if S[i] == T[j]:
				dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % MOD
			else:
				dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j]) % MOD
	print(dp[N][M])
solve()


P = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = [int(a) for a in input().split()]
T = [int(a) for a in input().split()]
X = [[1] * (M + 1)] + [[1] + [0] * M for _ in range(N)]
for i in range(N):
	for j in range(M):
		X[i + 1][j + 1] = (X[i + 1][j] + X[i][j + 1] - X[i][j] * (S[i] != T[j])) % P
print(X[N][M])


from functools import lru_cache
(N, M) = map(int, input().split())
S = tuple(map(int, input().split()))
T = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [1] * (M + 1)
for (i, s) in enumerate(S, start=1):
	ndp = [None] * (M + 1)
	ndp[0] = 1
	for (j, t) in enumerate(T, start=1):
		if s == t:
			ndp[j] = dp[j] + ndp[j - 1]
		else:
			ndp[j] = dp[j] + ndp[j - 1] - dp[j - 1]
	dp = ndp
print(ndp[-1] % MOD)


(N, M, *L) = map(int, open(0).read().split())
S = L[:N]
T = L[N:]
MOD = 10 ** 9 + 7
dp = [[0] * (M + 1) for i in range(N + 1)]
for i in range(N + 1):
	dp[i][0] = 1
for j in range(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
print(dp[N][M])


import sys
input = sys.stdin.readline
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 i in range(n + 1)]
for i in range(n):
	for j in range(m):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
		else:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
		dp[i + 1][j + 1] %= mod
print(dp[n][m])


(N, M) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = []
for i in range(len(s) + 1):
	dp.append([0] * (len(t) + 1))
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] + 1) % MOD
		else:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
print((dp[len(s)][len(t)] + 1) % MOD)


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[1] * (m + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(m):
		dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j]
		dp[i + 1][j + 1] %= mod
		if s[i] == t[j]:
			dp[i + 1][j + 1] += dp[i][j]
			dp[i + 1][j + 1] %= mod
print(dp[n][m])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
W = [1] * (N + 1)
for (i, t) in enumerate(T):
	W2 = W[:]
	k = 0
	for (j, s) in enumerate(S):
		if t == s:
			k += W[j]
		W2[j + 1] = (W[j + 1] + k) % mod
	W = W2
print(W[-1])


(N, M) = map(int, input().split())
MOD = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))
DP = [[1] * (M + 1) for i in range(N + 1)]
for i in range(N):
	hoge = 0
	for j in range(M):
		if S[i] == T[j]:
			hoge += DP[i][j]
			hoge %= MOD
		DP[i + 1][j + 1] = (DP[i][j + 1] + hoge) % MOD
print(DP[-1][-1])


(N, M) = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
d = [[0 for i in range(M + 1)] for j in range(N + 1)]
mod = 1000000007
for i in range(1, N + 1):
	sum = 0
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			sum += d[i - 1][j - 1] + 1
		d[i][j] = (d[i - 1][j] + sum) % mod
print((d[N][M] + 1) % mod)


MOD = 1000000007
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0 for j in range(M + 1)] for i in range(N + 1)]
for i in range(N + 1):
	dp[i][0] = 1
for j in range(M + 1):
	dp[0][j] = 1
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
		else:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
		dp[i + 1][j + 1] %= MOD
print(dp[-1][-1])


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0 for k in range(M + 1)] for l in range(N + 1)]
for k in range(N):
	for l in range(M):
		if S[k] == T[l]:
			dp[k + 1][l + 1] = dp[k + 1][l] + dp[k][l + 1] + 1
		else:
			dp[k + 1][l + 1] = dp[k + 1][l] + dp[k][l + 1] - dp[k][l]
		dp[k + 1][l + 1] %= MOD
print(dp[N][M] + 1)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
	for j in range(m + 1):
		if i == 0 or j == 0:
			dp[i][j] = 1
		else:
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
			if S[i - 1] == T[j - 1]:
				dp[i][j] += dp[i - 1][j - 1]
			dp[i][j] %= MOD
ans = dp[n][m]
print(ans)


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
(N, M) = MI()
S = [0] + LI()
T = [0] + LI()
mod = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i] == T[j]:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1
		else:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		dp[i][j] %= mod
print(dp[N][M] + 1)


mod = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = input().split()
T = input().split()
dp = [[0] * (M + 2) for _ in range(N + 2)]
for i in range(N + 1):
	dp[i][0] = 1
for j in range(M + 1):
	dp[0][j] = 1
for (i, s) in enumerate(S, 1):
	for (j, t) in enumerate(T, 1):
		dp[i][j] += dp[i - 1][j]
		dp[i][j] += dp[i][j - 1]
		if s == t:
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] -= dp[i - 1][j - 1]
		dp[i][j] += mod
		dp[i][j] %= mod
print(dp[N][M])


import numpy as np
(N, M) = list(map(int, input().split()))
S = np.array(list(map(int, input().split())))
T = np.array(list(map(int, input().split())))
MOD = 10 ** 9 + 7
neq = S[:, None] != T[None, :]
dp = np.ones(M + 1, dtype=np.int64)
for i in range(N):
	new_dp = dp.copy()
	new_dp[1:] -= dp[:-1] * neq[i]
	np.cumsum(new_dp, out=new_dp)
	dp = new_dp % MOD
print(dp[M])


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
slist = list(map(int, input().split()))
tlist = list(map(int, input().split()))
(dp, dp_sum) = ([], [])
for i in range(N + 1):
	dp.append([0] * (M + 1))
	dp_sum.append([1] * (M + 1))
dp[0][0] = 1
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if slist[i - 1] == tlist[j - 1]:
			dp[i][j] = dp_sum[i - 1][j - 1]
		dp_sum[i][j] = (dp[i][j] + dp_sum[i - 1][j] + dp_sum[i][j - 1] - dp_sum[i - 1][j - 1]) % MOD
print(dp_sum[-1][-1])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
import numpy as np
t = np.array(t, dtype=np.int64)
dp = np.ones(m + 1, dtype=np.int64)
for a in s:
	dp[1:] = ((dp[:-1] * (t == a)).cumsum() + dp[1:]) % mod
print(dp[-1])


import sys
from math import ceil

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def finput():
	return float(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())

def nok(a, b):
	m = a * b
	while a != 0 and b != 0:
		if a > b:
			a %= b
		else:
			b %= a
	return m // (a + b)

def main():
	mod = 1000000000.0 + 7
	(n, m) = rinput()
	s = rlinput()
	t = rlinput()
	a = [1] * (m + 1)
	for j in s:
		d = a[:]
		k = 0
		for (i, v) in enumerate(t):
			d[i] = (k + d[i]) % mod
			if j == v:
				k = (k + a[i]) % mod
		d[-1] = (k + d[-1]) % mod
		a = d[:]
	print(int(a[-1]))
main()


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def read_int():
	return int(input())

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

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(N, M, S, T):
	MOD = 10 ** 9 + 7
	dp0 = [1] * (M + 1)
	for s in S:
		dp1 = dp0[:]
		k = 0
		for (j, t) in enumerate(T):
			if s == t:
				k += dp0[j]
			dp1[j + 1] = (dp0[j + 1] + k) % MOD
		dp0 = dp1
	return dp0[-1]

def main():
	(N, M) = read_int_n()
	S = read_int_n()
	T = read_int_n()
	print(slv(N, M, S, T))

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
S_array = list(map(int, input().split()))
T_array = list(map(int, input().split()))
mod = 10 ** 9 + 7
add_num_array = [0] * N
ans_array = [0] * (N + 1)
ans_old = [1] * (N + 1)
for t in T_array:
	ans_array = [1] * (N + 1)
	for (i, s) in enumerate(S_array):
		if s == t:
			add_num_array[i] = (add_num_array[i] + ans_old[i]) % mod
		ans_array[i + 1] = (ans_array[i] + add_num_array[i]) % mod
	ans_old = ans_array
print(ans_array[-1])


MOD = 1000000007
(n, m) = map(int, input().split())
S = [int(_) for _ in input().split()]
T = [int(_) for _ in input().split()]
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(n + 1):
	dp[i][0] = 1
for j in range(m + 1):
	dp[0][j] = 1
for i in range(n):
	for j in range(m):
		if S[i] != T[j]:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
			dp[i + 1][j + 1] %= MOD
		else:
			dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
			dp[i + 1][j + 1] %= MOD
print(dp[n][m] % MOD)


(N, M) = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if s_list[i - 1] == t_list[j - 1]:
			dp[i][j] += dp[i - 1][j - 1] + 1
			dp[i][j] %= mod
		dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		dp[i][j] %= mod
print((dp[N][M] + 1) % mod)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, m) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	C = [[0] * (m + 1) for _ in range(n + 1)]
	from itertools import product
	for (i, j) in product(range(n), range(m)):
		dp = C[i][j] + 1 if S[i] == T[j] else 0
		C[i + 1][j + 1] = dp + C[i][j + 1] + C[i + 1][j] - C[i][j]
		C[i + 1][j + 1] %= MOD
	print(C[n][m] + 1)
resolve()


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
S.append(-1)
T = list(map(int, input().split()))
T.append(0)
mod = 10 ** 9 + 7
dp0 = [[0] * 2005 for _ in range(2005)]
dp1 = [[0] * 2005 for _ in range(2005)]
dp0[0][0] = 1
for i in range(N + 1):
	for j in range(M + 1):
		dp0[i + 1][j] += dp0[i][j] % mod
		dp1[i][j] += dp0[i][j] % mod
		dp1[i][j + 1] += dp1[i][j] % mod
		if S[i] == T[j]:
			dp0[i + 1][j + 1] += dp1[i][j] % mod
ans = dp1[N][M] % mod
print(ans)


(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M + 1)
acc = [0] * M
MOD = 10 ** 9 + 7
for s in S:
	ndp = [1]
	for (i, t) in enumerate(T):
		if s == t:
			ndp.append(ndp[-1] + dp[i + 1])
			acc[i] = dp[i + 1]
		else:
			ndp.append(ndp[-1] + acc[i])
	dp = ndp
print(dp[-1] % MOD)


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [0 for i in range(m)]
mod = 10 ** 9 + 7
for si in s:
	memo = [0]
	for (i, ti) in enumerate(t):
		memo.append((memo[-1] + dp[i]) % mod)
	for (i, ti) in enumerate(t):
		if si == ti:
			dp[i] += memo[i] + 1
			dp[i] %= mod
ans = 1
for dpi in dp:
	ans += dpi
	ans %= mod
print(ans)


def main():
	mod = 10 ** 9 + 7
	(N, M) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	V = [1] * N
	for t in T:
		(p, q) = (1, 1)
		for (i, (s, v)) in enumerate(zip(S, V)):
			V[i] = q = v + q if s == t else v + q - p
			p = v
	return V[-1] % mod
print(main())


mod = int(1000000000.0 + 7)
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = []
for i in range(len(s) + 1):
	dp.append([0] * (len(t) + 1))
for i in range(1, len(s) + 1):
	for j in range(1, len(t) + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = (1 + dp[i - 1][j] + dp[i][j - 1]) % mod
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod
ans = dp[-1][-1] + 1 % mod
print(ans)


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (m + 1) for _ in range(n + 1)]
for (i, ei) in enumerate(s, 1):
	for (j, ej) in enumerate(t, 1):
		if ei == ej:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1
		else:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		dp[i][j] %= mod
ans = dp[n][m] + 1
ans %= mod
print(ans)


import numpy as np
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = np.array(input().split(), dtype=np.int32)
T = np.array(input().split(), dtype=np.int32)
dp = np.ones(M + 1, dtype=np.int64)
for n in range(N):
	dp[1:] = ((dp[:-1] * (T == S[n])).cumsum() + dp[1:]) % MOD
answer = dp[M]
print(answer)


from collections import defaultdict

def solve():
	ans = 0
	mod = 10 ** 9 + 7
	s = defaultdict(lambda : -1)
	t = defaultdict(lambda : -1)
	(N, M) = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	dp = [[0] * (M + 1) for _ in range(N + 1)]
	for j in range(M + 1):
		dp[0][j] = 1
	for i in range(1, N + 1):
		dp[i][0] = 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 - 1][j] + dp[i][j - 1]
			else:
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
			dp[i][j] %= mod
	ans = dp[-1][-1] % mod
	return ans
print(solve())


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
sm = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N + 1):
	sm[i][0] = 1
for j in range(M + 1):
	sm[0][j] = 1
for i in range(1, N + 1):
	for j in range(1, M + 1):
		tmp = sm[i - 1][j - 1] if S[i - 1] == T[j - 1] else 0
		sm[i][j] = (sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1] + tmp) % MOD
print(sm[N][M])


from numpy import array, ones
mod = 10 ** 9 + 7
(N, M, *ST) = map(int, open(0).read().split())
(S, T) = (ST[:N], array(ST[N:]))
dp = ones(M + 1, dtype='int64')
for s in S:
	dp[1:] = ((dp[:-1] * (s == T)).cumsum() + dp[1:]) % mod
print(dp[-1])


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
MOD = 10 ** 9 + 7
(N, M) = lr()
S = ['?'] + lr()
T = ['.'] + lr()
dp = [[1] * (M + 1) for _ in range(N + 1)]
for j in range(1, M + 1):
	for i in range(1, N + 1):
		dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		if S[i] == T[j]:
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] %= MOD
answer = dp[N][M]
print(answer % MOD)


DIVS = 1000000007

def LI():
	return [int(x) for x in input().split()]
(N, M) = LI()
SS = LI()
TT = LI()
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if SS[i - 1] != TT[j - 1]:
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % DIVS
print((dp[N][M] + 1) % DIVS)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N + 1):
	dp[i][0] = 1
for j in range(M + 1):
	dp[0][j] = 1
for (i, a) in enumerate(A, start=1):
	for (j, b) in enumerate(B, start=1):
		if a == b:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD
print(dp[N][M])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
MOD = 1000000007
dp = [[0] * m for _ in range(n)]
for (i, si) in enumerate(s):
	for (j, tj) in enumerate(t):
		if i > 0:
			dp[i][j] += dp[i - 1][j]
		if j > 0:
			dp[i][j] += dp[i][j - 1]
		if si == tj:
			dp[i][j] += 1
		elif i > 0 and j > 0:
			dp[i][j] -= dp[i - 1][j - 1]
		dp[i][j] %= MOD
print((dp[n - 1][m - 1] + 1) % MOD)


from collections import deque
from itertools import repeat
MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
S = tuple(map(int, input().split()))
T = tuple(map(int, input().split()))
if N < M:
	(N, M) = (M, N)
	(S, T) = (T, S)
dp = deque(repeat(1, M + 1), M + 2)
for s in S:
	dp.append(1)
	for t in T:
		if s == t:
			dp.append(dp[1] + dp[-1])
		else:
			dp.append(dp[1] - dp[0] + dp[-1])
print(dp[-1] % MOD)


import sys
input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7

def main():
	(n, m) = map(int, input().split())
	(*s,) = map(int, input().split())
	(*t,) = map(int, input().split())
	dp = [[1] * (m + 1)] + [[1] + [0] * m for _ in range(n)]
	for i in range(n):
		for j in range(m):
			dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j] * (s[i] != t[j])) % mod
	print(dp[n][m])
main()


def getlist():
	return list(map(int, input().split()))
(N, M) = getlist()
S = getlist()
T = getlist()
L = [[1 for i in range(N + 1)] for j in range(M + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			L[j][i] = (L[j - 1][i] + L[j][i - 1]) % 1000000007
		else:
			L[j][i] = (L[j - 1][i] + L[j][i - 1] - L[j - 1][i - 1]) % 1000000007
print(L[M][N] % 1000000007)