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

Solution (Python):



import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]

dp[0][0] = 0


for i in range(n + 1):
    for j in range(m + 1):
        
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            
            
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)

Solution (Python):
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
mod=pow(10,9)+7
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=sum((dp[i][j+1],dp[i+1][j],-dp[i][j]))%mod
    if s[i]==t[j]:dp[i+1][j+1]+=dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])

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

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

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s
	
	def search(self, x):
		n, nums = self.n, self.nums
		s, p = 0, 0
		for i in range(n.bit_length(), -1, -1):
			np = p + (1<<i)
			if np <= n and s+nums[np] < x:
				s += nums[np]
				p = np
		return p

N, M = rl()
S = rl()
T = rl()

h = defaultdict(list)
for i, t in enumerate(T):
	h[t].append(i)
bit = BIT(M+1)
for i, s in enumerate(S):
	vals = []
	for j in h[s]:
		vals.append((j, bit.sum(j)+1))
	for j, v in vals:
		bit.add(j+1, v%mod)
print((bit.sum(M)+1)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    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 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]%=mod
    print(dp[-1][-1])
    

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

dp = [[0]*(M+1) for i in range(N+1)]
dps = [[0]*(M+1) for i in range(N+1)]
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            dp[n+1][m+1] = (dps[n][m]+1)%mod
        dps[n+1][m+1] = (dp[n+1][m+1]+dps[n+1][m]+dps[n][m+1]-dps[n][m])%mod

print(dps[-1][-1]+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)]
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]+1
        else:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]-dp[n][m]
        dp[n+1][m+1] %= mod

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

Solution (Python):
def count_cs(str1, str2, MOD):
    """文字列str1, str2の共通部分列(Common Subsequence, CS)を数え上げる。
    添字が異なる場合は異なる部分列として考える。
    計算量 O(|str1||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


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


print(count_cs(s, t, MOD))

Solution (Python):
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)]
sum = [[0] * (m + 1) for _ in range(n + 1)]
MOD = 10 ** 9 + 7

ans = 0
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = (sum[i][j] + 1) % MOD
    else:
      dp[i + 1][j + 1] = 0
    sum[i + 1][j + 1] = (sum[i][j + 1] + sum[i + 1][j] 
                       - sum[i][j] + dp[i + 1][j + 1]) % MOD
    ans += dp[i + 1][j + 1]
    ans %= MOD
print((ans + 1) % MOD)

Solution (Python):


LI = lambda: list(map(int, input().split()))


N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * (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][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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 i 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(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])

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

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    s = lmi()
    t = lmi()
    
    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+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])


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    N, M = list(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)]
    sdp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for n, s in enumerate(S):
        for m, t in enumerate(T):
            sdp_val = sdp[n][m]
            new_dp_val = (sdp_val + 1) if s == t else 0
            dp[n + 1][m + 1] = new_dp_val % MOD
            sdp[n + 1][m + 1] = (sdp[n][m + 1] + sdp[n + 1][m] - sdp_val + new_dp_val) % MOD
    print((sdp[N][M] + 1) % MOD)  


if __name__ == '__main__':
    main()

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

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    S = read_list()
    T = read_list()

    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

    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] if S[i] != T[j] else 0)) % mod
    
    print(dp[N][M])


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit

MOD = 10 ** 9 + 7

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

@njit
def solve(N, M, S, T):
    dp = np.ones((N+1, M+1), np.int64)
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            if s != t:
                dp[i+1][j+1] -= dp[i][j]
            dp[i+1][j+1] %= MOD
    return dp[N][M]

print(solve(N, M, S, T))

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 = [[1] * (M+1) for _ in range(N+1)]

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

print(dp[N][M])

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

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

Solution (Python):
N,M= map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
mod=10**9+7
ans=[[0 for e in range(M)] for f in range(N)]
rui=[[0 for e in range(M)] for f in range(N)]
for j in range(M):
 if j!=0:
  rui[0][j]=rui[0][j-1]
 if S[0]==T[j]:
  ans[0][j]=1
  rui[0][j]+=ans[0][j]
for i in range(1,N):
 rui[i][0]=rui[i-1][0]
 if S[i]==T[0]:
  ans[i][0]=1
  rui[i][0]+=ans[i][0]
for i in range(1,N):
 for j in range(1,M):
  rui[i][j]=rui[i][j-1]+rui[i-1][j]-rui[i-1][j-1]
  if S[i]==T[j]:
   ans[i][j]=(rui[i-1][j-1]+1)
   rui[i][j]+=ans[i][j]
  rui[i][j]%=mod
print((rui[N-1][M-1]+1)%mod)

Solution (Python):
import collections
n,m = map(int, raw_input().split(' '))
s,t = map(int, raw_input().split(' ')), map(int, raw_input().split(' '))
dp,prefix = [[0 for j in range(len(t))] for i in range(len(s))], [[0 for j in range(len(t))] for i in range(len(s))]
total = 1
mod = (10 ** 9) + 7
for ii in range(len(s)):
	for jj in range(len(t)):
		if s[ii] == t[jj]:
			dp[ii][jj] = 1+ (prefix[ii-1][jj-1] if ii-1>=0 and jj-1>=0 else 0)
			total += dp[ii][jj]
			total %= mod
		prefix[ii][jj] += prefix[ii - 1][jj] if ii - 1 >=0 else 0
		prefix[ii][jj] += prefix[ii][jj - 1] if jj - 1 >=0 else 0
		prefix[ii][jj] -= prefix[ii - 1][jj - 1] if (jj - 1 >=0) and (ii-1) >=0 else 0
		prefix[ii][jj] += dp[ii][jj]
		prefix[ii][jj] %= mod
		
print total

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M = map(int, readline().split())
    
    
    S = [0] + [int(i) for i in readline().split()]
    T = [0] + [int(i) for i in readline().split()]
    
    
    

    
    

    
    
    
    
    

    

    dp = [[0 for _ in range(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
    
    
    P = int(1e9)+7
    for i in range(N):
        for j in range(M):
            if S[i+1] != T[j+1]:
                
                
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
                dp[i+1][j+1] %= P
            else:
                
                
                
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] 
                dp[i+1][j+1] %= P
    print(dp[N][M])
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    s = [int(x) for x in input().split()]
    t = [int(x) for x in input().split()]
    
    mod = pow(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(n):
        for j in range(m):
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
    
    print(dp[n][m])            
    
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

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, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        if ei == ej:
            dp[i][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

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)

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

Solution (Python):
def main():

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

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(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][j+1] + dp[i+1][j] - dp[i][j]
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= mod
    
    return dp[N][M] + 1

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

Solution (Python):
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp1 = [[0] * (m + 1) for _ in range(n + 1)] 
dp2 = [[0] * (m + 1) for _ in range(n + 1)] 

dp1[0][0] = 1
for i in range(n + 1):
    dp2[i][0] = 1
for j in range(m + 1):
    dp2[0][j] = 1

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp1[i+1][j+1] = dp2[i][j]
        else:
            dp1[i+1][j+1] = 0
        dp2[i+1][j+1] = (dp1[i+1][j+1] + dp2[i][j+1] + dp2[i+1][j] - dp2[i][j]) % (10 ** 9 + 7)


print(dp2[-1][-1])

Solution (Python):


import sys
sys.setrecursionlimit(10**8)
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 = [[0]*(M+1) for _ in range(N+1)]
rui = [[0]*(M+1) for _ in range(N+1)]
ans = 1
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1] = rui[i][j] + 1
            dp[i+1][j+1] %= MOD
            ans += dp[i+1][j+1]
            ans %= MOD    
        rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + dp[i+1][j+1]
        rui[i+1][j+1] %= MOD

print(ans)

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

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

Solution (Python):
import numpy as np

N, M = 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])

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

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

dp = [[0]*(M+1) for _ in range(N+1)]
accum = [[0]*(M+1) for _ in range(N+1)]
MOD = 10**9+7

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

ans = (sum(map(sum, dp))+1)%MOD
print(ans)

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

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

Solution (Python):
def 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 + 5) for _ in range(N + 5)]
    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-1]
            dp[i][j] += dp[i-1][j]
            dp[i][j] += dp[i][j-1]
            dp[i][j] -= dp[i-1][j-1]
            dp[i][j] %= MOD

    print(dp[N][M])


if __name__ == "__main__":
    main()

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

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

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


M = 10**9+7
n,m = map(int, input().split())
s = input().split()
t = input().split()
n = len(s)
m = len(t)
dp = [[0] * (m+2) for _ in range(n+2)] 
ss = [[0] * (m+2) for _ in range(n+2)] 

for i in range(n+2):
    dp[i][0] = 0
    ss[i][0] = 0
for j in range(m+2):
    dp[0][j] = 0
    ss[0][j] = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1]==t[j-1]:
            dp[i][j] += (ss[i][j] + 1)
            dp[i][j] %= M
        ss[i+1][j+1] = (-ss[i][j]+ss[i+1][j]+ss[i][j+1]+dp[i][j]) % M
print(ss[n+1][m+1]+1)

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

Solution (Python):
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[(m+1)*[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]%=(10**9+7)
print(dp[-1][-1])

Solution (Python):
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 [0]*(n+1)]
    for i in range(n+1):
        dp[i][m]=1
    for i in range(m+1):
        dp[n][i]=1
    for i in range(n-1,-1,-1):
        for j in range(m-1,-1,-1):
            dp[i][j]=(dp[i+1][j]+dp[i][j+1]-(s[i]!=t[j])*dp[i+1][j+1])%(10**9+7)
    print(dp[0][0])
main()