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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[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

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    s = list(map(int, readline().split()))
    t = list(map(int, readline().split()))

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

    for i, val_s in enumerate(s, 1):
        for j, val_t in enumerate(t, 1):
            num = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            if val_s == val_t:
                num += dp[i - 1][j - 1] + 1
            num %= MOD
            dp[i][j] = num

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


if __name__ == '__main__':
    main()

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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)]
    SUM=[[0]*(M+2) for _ in range(N+2)]
    ans=1
    for s in range(N):
        for t in range(M):
            if S[s]==T[t]:
                dp[s+1][t+1]=SUM[s+1][t+1]+1
                ans+=dp[s+1][t+1]
                ans%=MOD
            else:
                dp[s+1][t+1]=0
            SUM[s+2][t+2]=SUM[s+1][t+2]+SUM[s+2][t+1]-SUM[s+1][t+1]+dp[s+1][t+1]
            SUM[s+2][t+2]%=MOD
    print(ans)
    

if __name__ == '__main__':
    main()

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

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

print((SUM[N][M] + 1) % mod)

Solution (Python):

"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7


dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(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]%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


print(dp1[n][m]%mod)

Solution (Python):


def main():
    MOD = 10 ** 9 + 7

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

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

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

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()
    
    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):
            
            
            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[-1][-1])
    
    

main()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()
    
    dp=[[0]*(M+1) for _ in range(N+1)]
    dp[0][0]=1
    
    cumsum=[[0]*(M+2) for _ in range(N+2)]
    
    
    for i in range(1,N+2):
        cumsum[i][1]=1
    for j in range(1,M+2):
        cumsum[1][j]=1
    
    for i in range(N):
        for j in range(M):
            if S[i]==T[j]:
                dp[i+1][j+1]=(cumsum[i+1][j+1])%mod
                
            cumsum[i+2][j+2]=(cumsum[i+2][j+1]+cumsum[i+1][j+2]-cumsum[i+1][j+1]+dp[i+1][j+1])%mod
            
    print(cumsum[-1][-1])
    """
    for i in range(N+2):
        print(' '.join(map(str, cumsum[i])))
        
    for i in range(N+1):
        print(' '.join(map(str, dp[i])))"""

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()))
dp = [[0] * (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]) % MOD
        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) % MOD)

Solution (Python):
import math


class Solution:
    def solve(self, N: int, M: int, S, T):

        mod = 10**9 + 7

        N_MAX = 2005

        dp = [[0] * N_MAX for _ in range(N_MAX)]
        s = [[0] * N_MAX for _ in range(N_MAX)]

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

        return (s[N][M] + 1)


if __name__ == '__main__':

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

    
    solution = Solution()
    print(solution.solve(N, M, S, T))

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 si in range(1, n+1):
        for ti in range(1, m+1):
            if s[si-1] == t[ti-1]:
                dp[si][ti] += 1
                dp[si][ti] += dp[si-1][ti-1]
            dp[si][ti] += dp[si-1][ti] + dp[si][ti-1]
            dp[si][ti] -= dp[si-1][ti-1]
            dp[si][ti] %= MOD
    print(dp[n][m] + 1)



if __name__ == "__main__":
    main()

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

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

Solution (Python):
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 = [[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, S in enumerate(Ss, start=1):
        for j, T in enumerate(Ts, start=1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            if S == T:
                dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= MOD

    print(dp[N][M])


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=[(m+1)*[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][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])

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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)]
sumij=[[0]*(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]=sumij[i][j]+1
        else:
            dp[i+1][j+1]=0
        sumij[i+1][j+1]=(sumij[i][j+1]+sumij[i+1][j]-sumij[i][j]+dp[i+1][j+1])%mod
print((sumij[-1][-1]+1)%mod)

Solution (Python):


def main():
    MOD = 10 ** 9 + 7

    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)]  
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

    acc = [[0] * (M + 1) for _ in range(N + 1)]
    acc[0][0] = 0
    acc[0][1] = 0
    acc[1][0] = 0

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

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


sdp = [[0] * (M + 1) for _ in range(N + 1)]


dp[0][0] = 1
for i in range(N + 1):
    sdp[i][0] = 1
for j in range(M + 1):
    sdp[0][j] = 1

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

print(sdp[N][M])

Solution (Python):

from collections import defaultdict

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

        if s == t:
            dp[i + 1][j + 1] += dp[i][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 = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]

MOD = 10 ** 9 + 7


dp = [[0] * (M + 1) for _ in range(N + 1)]

def main():
    
    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):
        for j, t in enumerate(T):
            dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]

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

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

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

Solution (Python):


def resolve():
    MOD = int(1e9+7)
    N,M = map(int,input().split())
    S= list(map(int,input().split()))
    T= list(map(int,input().split()))
    dpt = [[0]*(M+1) for i in range(N+1)]

    sm = [[0]*(M+1) for i in range(N+1)]

    for i in range(N):
        for j in range(M):
            dpt[i+1][j+1]= sm[i][j]+1 if S[i]==T[j] else 0

            sm[i+1][j+1] = (sm[i][j+1]+sm[i+1][j]+dpt[i+1][j+1]-sm[i][j]+MOD)%MOD
    ans =0
    for dptr in dpt:
        for i in dptr:
            ans += i
            ans %= MOD

    print(ans+1)            



if __name__ == "__main__":
    resolve()

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

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):
		
		sumI = 0
		sumI = dp[i+1][j]



		
		sumJ = 0
		sumJ = dp[i][j+1]



		
		if s[i] == t[j]:
			dp[i+1][j+1] = (sumI + sumJ) % PR
		else:
			dp[i+1][j+1] = (sumI + sumJ - dp[i][j]) % PR



print(dp[n][m])

Solution (Python):

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

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

print(dp[N][M])

Solution (Python):
import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))

Solution (Python):
import numpy as np

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

Solution (Python):
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp0 = [[0 for i in range(m+2)] for j in range(n+2)]
dp1 = [[0 for i in range(m+2)] for j in range(n+2)]
dp0[0][0] = 1
mod = 10**9+7
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] = (dp0[i+1][j]+dp0[i][j])%mod
        dp1[i][j] = (dp1[i][j]+dp0[i][j])%mod
        dp1[i][j+1] = (dp1[i][j+1]+dp1[i][j])%mod
        if i != n and j != m and s[i] == t[j]:
            dp0[i+1][j+1] = (dp1[i+1][j+1]+dp1[i][j])%mod
print(dp1[n][m])

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            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[-1][-1] + 1)%MOD)

if __name__ =='__main__':
    main()

Solution (Python):
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 = [[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
        elif 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[-1][-1])

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

def main():
    N,M = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    MOD = 10**9+7
    
    num = [[0 for _ in range(M+1)] for _ in range(N+1)]
    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

    ans = 1
    for i in range(N):
        for j in range(M):
            if s[i] == t[j]:
                num[i+1][j+1] = (dp[i][j])%MOD
                ans += num[i+1][j+1]
            dp[i+1][j+1] = (dp[i][j+1]+dp[i+1][j]-dp[i][j]+num[i+1][j+1])%MOD
    
    print(ans%MOD)

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

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, es in enumerate(s, 1):
    for j, et in enumerate(t, 1):
        if es == et:
            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[n][m]
print(ans)

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

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

dp=[[1 for i in range(0,M)] for j in range(0,N)]
for j in range(0,M):
    if j==0:
        if S[0]==T[0]:
            dp[0][0]=2
    else:
        if S[0]==T[j]:
            dp[0][j]=(dp[0][j-1]+1)%(10**9+7)
        else:
            dp[0][j]=dp[0][j-1]%(10**9+7)

for i in range(0,N):
    for j in range(0,M):
        if j!=0:
            if S[i]==T[j]:
                data[i][j]=(data[i][j-1]+dp[i-1][j-1])%(10**9+7)
            else:
                data[i][j]=data[i][j-1]
        if i!=0:
            dp[i][j]=(dp[i-1][j]+data[i][j])%(10**9+7)

print(dp[N-1][M-1]%(10**9+7))

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        
        
        


ans = dp_cum[N][M] + 1
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 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] + 1) % mod
        else:
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % mod

ans = (dp[-1][-1]+1) % 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
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]
    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])

Solution (Python):
import copy
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp = [0 for i in range(max(n,m))]
mod = 10**9+7
if n > m:
    a = s
    b = t
else:
    a = t
    b = s
    c = copy.copy(n)
    n = copy.copy(m)
    m = copy.copy(c)
l = []
for i in range(m):
    now = b[i]
    bl = []
    for j in range(n):
        if now == a[j]:
            bl.append(j)
    l.append(bl)
for i in range(m):
    if len(l[i]) > 0:
        dp2 = copy.copy(dp)
        now1 = 0
        k = 0
        k1 = len(l[i])
        count = 0
        while k < k1:
            if now1 == l[i][k]:
                dp[now1] += 1
                dp[now1] += count
                dp[now1] %= mod
                k += 1
            count += dp2[now1]
            count %= mod
            now1 += 1
        
print((sum(dp)+1)%mod)

Solution (Python):

n,m=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]


for i in range(m+1):
    dp[0][i]=1
for i in range(n+1):
    dp[i][0]=1
dp[0][0]=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]=(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[n][m])

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

if __name__ == '__main__':
	main()

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

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

answer = dp_cum[N][M]
print(answer)

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