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 sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
S = list(map(int,readline().split()))
T = list(map(int,readline().split()))
DIV = 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):
    dp[i][j] += dp[i][j - 1]
    dp[i][j] += dp[i - 1][j]
    if S[i - 1] != T[j - 1]:
      dp[i][j] -= dp[i - 1][j - 1]
    dp[i][j] %= DIV

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

n,m = ma()
s = ips()
t = ips()
dp = [[0]*(m+1) for i in range(n+1) ] 
tot = [[0]*(m+1) for i 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][j]=tot[i-1][j-1]+1
        else:
            dp[i][j]=0
        tot[i][j] = (dp[i][j] + tot[i][j-1]+tot[i-1][j] -tot[i-1][j-1])%mod

print((tot[n-1][m-1]+1)%mod)

Solution (Python):
"""
愚直に全探索すると、O(2**N+2**M)かかる
制約的にはDPっぽいかな。
あ、これ部分文字列DPの発想に近いな。
dp[i][j] => Sのインデックスi、Tのインデックスjまでみる。インデックスi、インデックスjは使う。
nt[i][j] => Tのi項以降で数字jが出てくるインデックス。
"""
N,M = map(int,input().split())

N += 1
M += 1

S = list(map(int,input().split()))
S = [0]+S
T = list(map(int,input().split()))
T = [0]+T

dp = [[0]*M for _ in range(N)]
mod = 10**9 +7
for j in range(M):
    dp[0][j] = 1

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

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

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,M = MI()
S = [0] + LI()
T = [0] + LI()
mod = 10**9+7

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


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

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

Solution (Python):
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


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


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

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

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

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

print(dp[n][m])

Solution (Python):
import sys

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


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

    dp = [1] * (M + 1)

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

    print(dp[M])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


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

    dp = [1] * (M + 1)

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

    print(dp[M])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


def main():
    N, M = 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)]
    sdp = [[0] * (M + 2) for _ in range(N + 2)]

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

    print(sdp[N][M])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


def main():
    N, M = 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 in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

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

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


def main():
    N, M = 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)]
    dp[0][0] = 1
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            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 + 1][j + 1] + dp[i][j]) % MOD

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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] = 1
    for i in range(n + 1):
        for j in range(m + 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]
                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__':
    resolve()

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
 
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp_cum[0][0] = 1
for n in range(N+1):
    dp_cum[n][0] = 1
for m in range(M+1):
    dp_cum[0][m] = 1
  
for n in range(1,N+1):
    for m in range(1,M+1):
        now = 0
        if S[n] == T[m]:
            now = dp_cum[n-1][m-1]
        dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + now
        dp_cum[n][m] %= MOD
print(dp_cum[N][M])

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 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()))

S.append(0)
T.append(0)
MAX = 2005
dp0 = [[0] * MAX for _ in range(MAX)]
dp1 = [[0] * MAX for _ in range(MAX)]

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






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

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):
    dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j]*int(S[i]!=T[j]))%MOD

print(dp[-1][-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 = [[1]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1] == T[j-1]:
            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 = [[0] * (m + 1) for _ in range(n + 1)]
dpsum = [[0] * (m + 1) for _ in range(n + 1)]
mod = pow(10, 9) + 7
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = 1
            if not i == 1 and not j == 1:
                dp[i][j] += dpsum[i - 1][j - 1]
                dp[i][j] %= mod
        dpsum[i][j] = dpsum[i - 1][j] + dpsum[i][j - 1] - dpsum[i - 1][j - 1] + dp[i][j]
        dpsum[i][j] %= mod
ans = dpsum[n][m] + 1
print(ans)

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

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)]
total=[[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]=(total[i][j]+1)%mod
		total[i+1][j+1]=(total[i+1][j]+total[i][j+1]-total[i][j]+dp[i+1][j+1])%mod
print((total[-1][-1]+1)%mod)

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

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m = map(int,ipt().split())
    s = [int(i) for i in ipt().split()]
    t = [int(i) for i in ipt().split()]
    ans = 0

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

    return None

if __name__ == '__main__':
    main()