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

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

Solution (Python):
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N, M = inpl()
S = [0] + inpl()
T = [0] + inpl()

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

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

Solution (Python):
import sys
from collections import deque  
from collections import defaultdict  
from heapq import heapify, heappush, heappop, heappushpop  
from bisect import bisect_left, bisect_right  



s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

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

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            
            rui[i+1][j+1] = (rui[i+1][j] + rui[i][j+1] - rui[i][j] + c) % MOD
            n = (n + c) % MOD

    
    

    
    
    print(n)

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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))



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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))



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


print(ans)

Solution (Python):
import numpy as np

N,M = map(int,input().split())
MOD = 1e9 + 7
S = np.array(input().split())
T = np.array(input().split())

dp = np.zeros((N+1,M+1))
dp[0] = 1

for n in range(1,N+1):
    same = (T == S[n-1])
    dp[n,1:][same] = dp[n-1,:-1][same]
    dp[n] = (dp[n].cumsum() + dp[n-1])%MOD
    
print(int(dp[N,M]))

Solution (Python):

import sys
from pprint import pprint

MOD = 1000000007  

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    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 + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
            dp[i + 1][j + 1] %= MOD
    
    ret = dp[N][M]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    S = [ int(next(tokens)) for _ in range(N) ]  
    T = [ int(next(tokens)) for _ in range(M) ]  
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline

MOD = int(1e9 + 7)

def f(N, M, s, t):
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        cumsi = cums[i]
        cumsi1 = cums[i+1]
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = cumsi[j] + 1
            cumsi1[j+1] = \
                (cumsi1[j] + cumsi[j+1] - cumsi[j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Solution (Python):
N, M = map(int, input().split())
S = [int(i) for i in input().split()]+['g']
T = [int(i) for i in input().split()]+['a']

MOD = 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(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):
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
S = inpl()
T = inpl()

total = [0]*(N+1)*(M+1)
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			n = total[(M+1)*i+j] + 1
		else:
			n = 0
		total[(M+1)*(i+1)+(j+1)] = (n + total[(M+1)*i+(j+1)] + total[(M+1)*(i+1)+j] - total[(M+1)*i+j]) % MOD
print((total[-1]+1) % MOD)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())


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

for r in range(1, N+1):
    for k in range(1, M+1):
        if S[r-1] == T[k-1]:
            dp[r][k] = 1+dp[r-1][k]+dp[r][k-1]
            dp[r][k] %= MOD
        else:
            dp[r][k] = dp[r-1][k]+dp[r][k-1]-dp[r-1][k-1]
            dp[r][k] %= MOD
print((dp[-1][-1]+1) % MOD)

Solution (Python):

MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[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] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

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

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = np.array([-1] + S)
T = np.array([-1] + T)



















cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    cumsum[1:] += ((T == S[i])[1:] * cumsum[:-1] % MOD).cumsum()
    cumsum %= MOD
print(cumsum[-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 _ 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 + 1][j]
        dp[i + 1][j + 1] += dp[i][j + 1]
        dp[i + 1][j + 1] += -dp[i][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 = 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)]
s = [[0] * (M + 1) for i in range(N + 1)]
dp[0][0] = 1

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

ans = 0
for i in range(N + 1):
    for j in range(M + 1):
        ans += dp[i][j]
        ans %= MOD
print(ans)

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

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

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

print(ans)

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

Solution (Python):
N, M = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if s_list[i - 1] == t_list[j - 1]:
            dp[i][j] += dp[i - 1][j - 1] + 1
            dp[i][j] %= mod
        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) % mod)

Solution (Python):
def e_common_subsequence(N, M, S, T, MOD=10**9 + 7):
    
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    total = [[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] = (total[i][j] + 1) % MOD
                ans = (ans + dp[i + 1][j + 1]) % MOD
            total[i + 1][j + 1] = (total[i][j + 1] + total[i + 1][j]
                                   - total[i][j] + dp[i + 1][j + 1] + MOD) % MOD
    return ans

N, M = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
print(e_common_subsequence(N, M, S, T))

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

mod = 10 ** 9 + 7


def solve(x, y):
    dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] += dp[i - 1][j - 1] + 1
                dp[i][j] %= mod
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod

    return dp


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

Solution (Python):
M = int(1e+9 + 7)


def main():
  input()
  s = list(map(int, input().split()))
  t = list(map(int, input().split()))
  z = [0] * len(t)

  for v in s:
    c = 0

    for i, w in enumerate(t):
      y = z[i]

      if v == w:
        z[i] = (z[i] + c + 1) % M

      c = (c + y) % M

  y = 0

  for v in z:
    y = (y + v) % M

  y = (y + 1) % M

  print(y)


if __name__ == '__main__':
  main()

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

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


N, M = mi()
Ss = list(mi())
Ts = list(mi())
slen = len(Ss)
tlen = len(Ts)



DP_pairs = [[0] * (len(Ts)+1) for _ in range(len(Ss)+1)] 
DP_cumsum = [[0] * (len(Ts)+1) for _ in range(len(Ss)+1)] 


for i, s in enumerate(Ss):
  i += 1 
  for j, t in enumerate(Ts):
    j += 1 
    if s==t:
      DP_pairs[i][j] = DP_cumsum[i-1][j-1] + 1
    
    DP_cumsum[i][j] = (DP_cumsum[i][j-1]+DP_cumsum[i-1][j]-DP_cumsum[i-1][j-1]+DP_pairs[i][j])%(10**9+7)

print(DP_cumsum[len(Ss)][len(Ts)]+1)

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 i in range(N+1)]
mod=10**9+7
for n in range(1,N+1):
    for m in range(1,M+1):
        x=1 if S[n-1]==T[m-1] else -dp[n-1][m-1]
        y=dp[n-1][m]+dp[n][m-1]+x
        dp[n][m]=y if y<mod else y-mod
print((dp[-1][-1]+1)%mod)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    Q = 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)]
    memo = [ [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+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce

NNN = 10 ** 9 + 7


def main():
    N, M = [int(a) for a in input().split()]
    S = [int(a) for a in input().split()]
    T = [int(a) for a in input().split()]

    table = [0] * M

    for si in reversed(S):
        c = 0
        for i in reversed(range(M)):
            prev_score = table[i]
            if T[i] == si:
                table[i] = (table[i] + c + 1) % NNN
            c = (c + prev_score) % NNN

    s = 1
    for a in table:
        s = (s + a) % NNN
    print(s)


if __name__ == '__main__':
    main()

Solution (Python):



N, M = list(map(int, input().rstrip().split(' ')))
S = list(map(int, input().rstrip().split(' ')))
T = list(map(int, input().rstrip().split(' ')))
dp = [[0] * (N + 1) for _ in range(M + 1)]

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

Solution (Python):


def main():
    Q = 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)]
    memo = [ [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+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+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()))

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

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

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

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

Solution (Python):
def e_common_subsequence(N, M, S, T, MOD=10**9 + 7):
    
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    total = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        total[i][0] = 1
    for j in range(M + 1):
        total[0][j] = 1

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

N, M = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
print(e_common_subsequence(N, M, S, T))

Solution (Python):
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,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            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):
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,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            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])%mod)

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

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



			dp[i][j]+=1
		Sum[i][j]=(Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+dp[i][j])%mod

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

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

dp = [[None] * m for _ in range(n)] 
sumdp = [[None] * m for _ in range(n)]

if s[0] == t[0]:
    dp[0][0] = 1
    sumdp[0][0] = 2
else:
    dp[0][0] = 0
    sumdp[0][0] = 1
    

for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
        
        sumdp[i][0] = sumdp[i-1][0] + 1
        sumdp[i][0] %= q
        
        
        
    else:
        dp[i][0] = 0
        sumdp[i][0] = sumdp[i-1][0]
        
for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
        sumdp[0][j] = sumdp[0][j-1] + 1
        sumdp[0][j] %= q
    else:
        dp[0][j] = 0
        sumdp[0][j] = sumdp[0][j-1]
        
for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = sumdp[i-1][j-1]
        else:
            dp[i][j] = 0
        sumdp[i][j] = dp[i][j] + sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %= q

print(sumdp[n-1][m-1])

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**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 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)%mod
        else:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]-dp[n][m]

print((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()))
mod = 10**9+7

dp = [[0 for i in range(M)] for j in range(N)]
sum_dp = [[0 for i in range(M)] for j in range(N)]


if S[0] == T[0]:
    dp[0][0] = 1
    sum_dp[0][0] = 1

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

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

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

print((sum_dp[N-1][M-1]+1)%mod)

Solution (Python):
N,M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10**9 + 7

x = 2160
dp = [[0]*x for i in range(x)]
sum2d = [[0]*x for i in range(x)]
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = sum2d[i][j] + 1
        sum2d[i+1][j+1] = (dp[i+1][j+1]+sum2d[i][j+1]+sum2d[i+1][j]-sum2d[i][j])%mod
print((sum2d[N][M]+1)%mod)

Solution (Python):

import numpy as np

MOD = 10**9+7
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype=np.int32)
dp = np.ones(M+1, dtype=np.int64)

for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % MOD

print(dp[M])

Solution (Python):

MOD = 10**9+7
N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))

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 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):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      
      dp[n][m] = 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] + dp[n][m]
    dp_cum[n][m] %= MOD

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

Solution (Python):
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=[1]*(m+1)
for i in range(n):
    b=a[:]
    k=0
    for j in range(m):
        b[j]=(k+b[j])%(10**9+7)
        if s[i]==t[j]:
            k=(k+a[j])%(10**9+7)
    b[-1]=(k+b[-1])%(10**9+7)
    a=b[:]
print(a[-1]%(10**9+7))

Solution (Python):
from collections import deque
from itertools import repeat

MOD = 10**9 + 7

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

if N < M:
    N,M = M,N
    S,T = T,S

dp = deque(repeat(1, M+1), M+2)


for s in S:
    dp.append(1)
    for t in T:
        if s == t:
            dp.append(dp[1]+dp[-1])
        else:
            dp.append(dp[1]-dp[0]+dp[-1])

print(dp[-1]%MOD)

Solution (Python):
from collections import deque
from itertools import repeat

MOD = 10**9 + 7

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

if N < M:
    N,M = M,N
    S,T = T,S

dp = deque(repeat(1, M+1), M+2)


for s in S:
    dp.append(1)
    for t in T:
        if s == t:
            dp.append(dp[1]+dp[-1])
        else:
            dp.append(dp[1]-dp[0]+dp[-1])

print(dp[-1]%MOD)

Solution (Python):


import sys

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

N,M=MAP()
S=LIST()
T=LIST()


dp=list3d(N+2, M+2, 2, 0)
dp[0][0][0]=1
for i in range(N+1):
    for j in range(M+1):
        dp[i][j][0]%=MOD
        
        dp[i+1][j][0]+=dp[i][j][0]
        dp[i][j][1]+=dp[i][j][0]
        dp[i][j+1][1]+=dp[i][j][1]
        
        if i<N and j<M and S[i]==T[j]:
            
            dp[i+1][j+1][0]+=dp[i][j][1]
print((dp[N][M][1])%MOD)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MAT(h): return [list(map(int, input().split())) for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10**9 + 7

x = 2160
dp = [[0]*x for i in range(x)]
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] + 1) % mod
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%mod

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

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