Problem:
 Score : 500 points    Problem Statement 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 1 2 2
1 3
3 1      Sample Output 1 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.       Sample Input 2 2 2
1 1
1 1      Sample Output 2 6  S has four subsequences: (), (1), (1), (1, 1) .  T has four subsequences: (), (1), (1), (1, 1) .  There are 1 \times 1 pair of subsequences in which the subsequences are both () , 2 \times 2 pairs of subsequences in which the subsequences are both (1) , and 1 \times 1 pair of subsequences in which the subsequences are both (1,1) , for a total of six pairs.
Note again that 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.       Sample Input 3 4 4
3 4 5 6
3 4 5 6      Sample Output 3 16       Sample Input 4 10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7      Sample Output 4 191       Sample Input 5 20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1      Sample Output 5 846527861  Be sure to print the number modulo 10^9+7 .

Solution (Python):
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])

Solution (Python):
import numpy as np
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 s in S:
  dp[1:] = ((dp[:-1] * (T == s)).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
S=[0]+LIST()
T=[0]+LIST()

dp = [[0] * (M+1) for i 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] == T[j]:
            
            dp[i][j]+=dp[i-1][j-1]+1
            dp[i][j]%=MOD

print((dp[N][M]+1)%MOD)

Solution (Python):
import numpy as np
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 s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

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

Solution (Python):
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:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

S = l()
T = l()

dp = [ [0 for i in range(n+1)]  for j in range(m+1)]

for i in range(n+1):
    dp[0][i] = 1
for i in range(m+1):
    dp[i][0] = 1

for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            dp[j+1][i+1] += dp[j][i]
        dp[j+1][i+1] +=dp[j+1][i] + dp[j][i+1] - dp[j][i]
        dp[j+1][i+1] %= 10**9+7
print(dp[-1][-1])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline

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.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)

Solution (Python):
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.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)

Solution (Python):
N,M = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]+[0]
T = [int(x) for x in input().split()]+[0]
MOD = 10**9+7
dp=[[[0]*2 for _ in range(M+2)] for _ in range(N+2)]
dp[0][0][0]=1
for i in range(N+1):
    for j in range(M+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][0] %= MOD
        dp[i][j][1] += dp[i][j][0]
        dp[i][j][1] %= MOD
        dp[i][j+1][1] += dp[i][j][1]
        dp[i][j+1][1] %= MOD
        if(S[i]==T[j]):
            dp[i+1][j+1][0] += dp[i][j][1]
            dp[i+1][j+1][0] %= MOD

print(dp[N][M][1])

Solution (Python):
N, M = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

mod = 10 ** 9 + 7


def solve(x, y):
    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):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod
            if x[i - 1] == y[j - 1]:
                dp[i][j] += dp[i - 1][j - 1] + 1
                dp[i][j] %= mod
    return dp


ans = solve(s_list, t_list)
print((ans[N][M] + 1) % mod)

Solution (Python):
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])

Solution (Python):
MOD = pow(10, 9) + 7

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

dp = [[1 for _ in range(n+1)] for _ in range(m+1)]
for i, s in enumerate(slist):
  for j, t in enumerate(tlist):
    if s != t:
      dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD
    else:
      
        dp[j+1][i+1] = (dp[j+1][i] + dp[j][i+1]) % MOD
      
      

print(dp[-1][-1])

Solution (Python):
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])

Solution (Python):
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 i in range(N+1)]
dp[0][0]=1
for i in range(N):
    dp[i+1][0]=1
for j in range(M):
    dp[0][j+1]=1
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1]+=dp[i][j]
        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])

Solution (Python):
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])

Solution (Python):
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)
 
if __name__ == '__main__':
    print(solve())

Solution (Python):


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)]
dp[0][0] = 0
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]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j] + 1
        dp[i + 1][j + 1] %= MOD

print(dp[n][m] + 1)

Solution (Python):
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)

Solution (Python):

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)

if __name__ == '__main__':
    print(solve())

Solution (Python):
n, m = map(int, input().split())
s = list(map(str, input().split()))
t = list(map(str, input().split()))
MOD = 10**9 + 7

def count_cs(str1, str2, MOD):
    '''
    計算量O(len(str1)*len(str2))
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + 1
            else:
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
            dp[i+1][j+1] %= MOD
    return (dp[len(str1)][len(str2)] + 1) % MOD

print(count_cs(s, t, MOD))

Solution (Python):

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


if __name__ == '__main__':
    main()

Solution (Python):
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])

Solution (Python):
def e_common_subsequence(N, M, S, T, 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 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]
            else:
                
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + MOD
            dp[i + 1][j + 1] %= MOD
    return 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()]
print(e_common_subsequence(N, M, S, T))

Solution (Python):

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


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

sid = defaultdict(list)
for i, s in reversed(list(enumerate(sss))):
    sid[s].append(i)

bit = Bit(n + 1)
bit.add(1, 1)

for t in ttt:
    if t not in sid:
        continue
    for i in sid[t]:
        bit.add(i + 2, bit.sum(i + 1))

print(bit.sum(n + 1))

Solution (Python):
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)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


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

bit = Bit(n + 1)
bit.add(1, 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1))

print(bit.sum(n + 1))

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

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):
        n  = tab[j+1][i] + tab[j][i+1] - tab[j+1][i+1]  
        n += tab[j+1][i+1] if tab[j][i] else 0  
        tab[j][i] = n % modulo

print(tab[0][0])

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return


def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return


def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return


def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return


def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j 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-1][j]+dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mod
            if dp[i][j] >= mod:
                dp[i][j] %= mod
    print(dp[n][m])
    return


def F():
    return


if __name__ == "__main__":
    E()

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

Solution (Python):
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 j in range(N+1)]
for j in range(M):
    dp[1][j + 1] = dp[1][j] + 1 if s[0] == t[j] else dp[1][j]

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

for i in range(1, N):
    for j in range(1, M):
        if s[i] == t[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)

Solution (Python):
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])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return


def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return


def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return


def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return


def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j 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-1][j]+dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] < 0 or dp[i][j] >= mod:
                dp[i][j] %= mod
    print(dp[n][m])
    return


def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = input().split()
        print(a,b,d)
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    ma = 100000000
    p = [0,ma/3,2*ma/3,ma]
    for i in range(100):
        x1 = [x[i]+f[i][0]*p[1] for i in range(n)]
        x2 = [x[i]+f[i][0]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        print(x1,p)
    a = sum(p)/4
    print(p)
    p = [-ma,2*ma/3-ma,2*ma/3*2-ma,ma]
    for i in range(100):
        x1 = [y[i]+f[i][1]*p[1] for i in range(n)]
        x2 = [y[i]+f[i][1]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
    b = sum(p)/4
    print(a,b)
    return


if __name__ == "__main__":
    E()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return


def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return


def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return


def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return


def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j 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-1][j]+dp[i][j-1]
            else:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] >= mod or 0 > dp[i][j]:
                dp[i][j] %= mod
    print(dp[n][m])
    return


def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = LS()
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    l = 0
    r = 100000000
    while r-l > 0.5:
        m = (l+r)/2
        px = [x[i]+f[i][0]*m for i in range(n)]
        py = [y[i]+f[i][1]*m for i in range(n)]
        dx = max(x)-min(x)
        dy = max(x)-min(y)
        if dx*dy < ans:
            ans = dx*dy

    return


if __name__ == "__main__":
    E()