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

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

Solution (Python):
N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)

Solution (Python):
MOD = 10**9+7
N, M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

dp = [[0] * (M + 1) for _ 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, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            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) % MOD
print(dp[-1][-1])

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


if __name__ == '__main__':
  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))

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())




MOD = 10**9 + 7



class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    
    
    
    

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    


COMBINATION_MAX = 2 * 10**5


class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）
        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）
        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）
        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, k)




def ABC021_D():
    n = ii()
    k = ii()
    res = Combination()
    print(res.H(n, k))





def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.C(N - K + 1, i))






def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)






def ABC130_E():
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(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:
                a[i][j] = Modint(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)
    print(a[N][M])






if __name__ == '__main__':
    
    
    
    ABC130_E()

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

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

Solution (Python):
import copy
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[0] = 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 = copy.deepcopy(ans_array)
    
print(ans_array[-1])

Solution (Python):
def main():
	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 = 10**9+7

	dp0 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp1 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp0[0][0] = 1
	for i in range(N+1):
		for j in range(M+1):
			dp0[i+1][j] += dp0[i][j]
			dp0[i+1][j] %= MOD
			dp1[i][j] += dp0[i][j]
			dp1[i][j] %= MOD
			dp1[i][j+1] += dp1[i][j]
			dp1[i][j+1] %= MOD

			if S[i] == T[j]:
				dp0[i+1][j+1] += dp1[i][j]
				dp0[i+1][j+1] %= MOD
	print(dp1[N][M])


if __name__ == '__main__':
	main()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())




MOD = 10**9 + 7



class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    '''

    def __init__(self, n, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n, self.mod)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return pow(self.n, self.mod - 2, self.mod)

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    
    
    
    

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    


class Combination():
    def __init__(self, sz):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [0] * (sz + 1)
        self._rfact = [0] * (sz + 1)
        self._fact[0] = 1
        self._rfact[sz] = 1
        for i in range(1, sz + 1):
            self._fact[i] = int(self._fact[i - 1] * Modint(i))
        self._rfact[sz] = Modint(self._fact[sz]).inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = int(self._rfact[i + 1] * Modint(i + 1))

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）
        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[n - k])

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）
        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[k] * self._rfact[n - k])

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）
        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, n)




def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))






def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)






def ABC130_E():
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(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:
                a[i][j] = Modint(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)
    print(a[N][M])






if __name__ == '__main__':
    
    
    ABC130_E()

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())




MOD = 10**9 + 7



class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    '''

    def __init__(self, n, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n, self.mod)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return pow(self.n, self.mod - 2, self.mod)

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    
    
    
    

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    


class Combination():
    def __init__(self, sz):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [0] * (sz + 1)
        self._rfact = [0] * (sz + 1)
        self._fact[0] = 1
        self._rfact[sz] = 1
        for i in range(1, sz + 1):
            self._fact[i] = int(self._fact[i - 1] * Modint(i))
        self._rfact[sz] = Modint(self._fact[sz]).inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = int(self._rfact[i + 1] * Modint(i + 1))

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）
        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[n - k])

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）
        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[k] * self._rfact[n - k])

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）
        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, n)




def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))






def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)






def ABC130_E():
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(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:
                a[i][j] = Modint(1)
            elif S[i - 1] != T[j - 1]:
                a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]
            else:
                a[i][j] = a[i - 1][j] + a[i][j - 1]
    print(a[N][M])


if __name__ == '__main__':
    
    
    ABC130_E()

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

Solution (Python):
def f(n, m):
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i, sk in enumerate(s):
        dpi1 = dp[i + 1] = dp[i][:]
        cs = 0
        for j, tk in enumerate(t):
            if sk == tk:
                cs = (cs + dp[i][j]) % md
            dpi1[j + 1] = (dpi1[j + 1] + cs) % md


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

md = 10 ** 9 + 7
n, m = map(int, input().split())
f(n, m)

Solution (Python):
def f(n, m):
    s = list(input().split())
    t = list(input().split())
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i, sk in enumerate(s):
        dpi1 = dp[i + 1] = dp[i][:]
        cs = 0
        for j, tk in enumerate(t):
            if sk == tk:
                cs = (cs + dp[i][j]) % md
            dpi1[j + 1] = (dpi1[j + 1] + cs) % md


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

md = 10 ** 9 + 7
n, m = map(int, input().split())
f(n, m)

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

Solution (Python):
MOD = 10**9 + 7


def main():
    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):
        dp[i][0] = 1
    for i in range(M+1):
        dp[0][i] = 1
    ans = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                cur = dp[i][j]
            else:
                cur = 0
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] +
                            - dp[i][j] + cur) % MOD

    print(dp[N][M])


if __name__ == "__main__":
    main()

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  
        x = (x+dp[z-1][j-1]+1)%R  
        acc[z] = x
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        
        
        
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)