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

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

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

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

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


for i in range(M+1):
    DP[i][0]=1

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

Solution (Python):
import itertools


DEF_MODULO = 10 ** 9 + 7


def solve(n, m, ss, ts, mod = DEF_MODULO):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i, j in itertools.product(range(n), range(m)):
        if ss[i] == ts[j]:
            dp[i + 1][j + 1] = 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
    return (dp[n][m] + 1) % mod


def main():
    n, m = (int(z) for z in input().split())
    ss = [int(s) for s in input().split()]
    ts = [int(t) for t in input().split()]
    res = solve(n, m, ss, ts)
    print(res)


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 = 1000000007
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(0, len(s) + 1):
    for j in range(0, len(t) + 1):
        ret = 0
        if i == 0:
            ret = 1
        elif j == 0:
            ret = 1
        else:
            ret = (dp[i][j - 1] + dp[i - 1][j]) % mod
            if s[i - 1] != t[j - 1]:
                ret = (ret + mod - dp[i - 1][j - 1]) % mod
        dp[i][j] = ret
print(dp[len(s)][len(t)])

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

print(dp[N][M])

Solution (Python):
N, M = map(int, input().split())
S_list = list(map(int, input().split()))
T_list = list(map(int, input().split()))

LARGE = 10**9+7

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



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

for i in range(N - 1, -1, -1):
    for j in range(M - 1, -1, -1):
        if S_list[i] == T_list[j]:
            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] = DP[i][j] % LARGE

print(DP[0][0])

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

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

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

for j in range(1,M+1):
        
    for i in range(1,N+1):
        if S[i-1]==T[j-1]:
            DP[j][i]=SUM[j-1][i-1]

    S2=0
    for i in range(1,N+1):
        S2=(S2+DP[j][i])%mod
        SUM[j][i]=(SUM[j-1][i]+S2)%mod
    

ANS=0
for i in range(M+1):
    ANS=(ANS+sum(DP[i]))%mod

print((ANS+1)%mod)

Solution (Python):
MOD = pow(10, 9) + 7

n, m = map(int, input().split())
slist = list(map(int, input().split()))
tlist = list(map(int, input().split()))

dp = [[1 for _ in range(n+1)] for _ in range(m+1)]
for i, s in enumerate(slist):
  for j, t in enumerate(tlist):
    if s != t:
      dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD
    else:
      if slist[i] == t and tlist[j] == s:
        dp[j+1][i+1] = (dp[j+1][i] + dp[j][i+1]) % MOD
      else:
        dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD

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

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

n,m = (int(num) for num in input().split())
s = [int(num) for num in input().split()]
t = [int(num) for num in 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):
        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] = dp[i][j] % MOD
        
        
print(dp[n][m])

Solution (Python):
MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    S = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    T = list(map(int, buflist))
    dp = []
    for i in range(N+1):
        dp.append([])
        for j in range(M+1):
            dp[i].append(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):




MOD = 1000000007


def main():
  N,M = map(int, input().split())
  Sn = list(map(int, input().split()))
  Tn = list(map(int, input().split()))

  
  dp = [[1 for m in range(M+1)] for n in range(N+1)]

  for n in range(N):
    for m in range(M):
      if Sn[n]==Tn[m]:
        dp[n+1][m+1] = (dp[n][m+1]+dp[n+1][m]) % MOD
      else:
        dp[n+1][m+1] = (dp[n][m+1]+dp[n+1][m]-dp[n][m]) % 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()))
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0]=1
for i in range(n+1):
    dp[0][i]=1
for i in range(m):
    for j in range(n):
        if s[j]==t[i]:
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%(10**9+7)
        else:
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
print(dp[-1][-1]%(10**9+7))

Solution (Python):
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[1 for i in range(n+1)] for j in range(m+1)]
ans=1
mod=10**9+7
for T in range(1,m+1):
    for S in range(1,n+1):
        tmp=dp[T-1][S-1]
        if(s[S-1]==t[T-1]):
            dp[T][S]=(dp[T-1][S]+dp[T][S-1])%mod
        else:
            dp[T][S]=(dp[T-1][S]+dp[T][S-1]-tmp)%mod
print(dp[-1][-1])

Solution (Python):
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
ans = 0
mod = 10**9+7
C = [1]*(N+1)
for t in T:
    d = 0
    for i, s in enumerate(S):
        d_ = C[i]
        if t==s:
            ans = (ans + d_) % mod

        C[i] += d
        C[i] %= mod
        if t==s:
            d += d_
            d %= mod
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 = [[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):
        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

ans = dp[N][M]
print(ans)

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

Solution (Python):
n,m = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

DP = [[[0,0] for i in range(m)] for j in range(n)]

mod=10**9+7

if S[0]==T[0]:
    DP[0][0][0]=1
    DP[0][0][1]=1

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

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

for i in range(1,n):
    for j in range(1,m):
        if S[i]==T[j]:
            DP[i][j][0] = (DP[i-1][j-1][1]+1)%mod
        DP[i][j][1] = (DP[i-1][j][1]+DP[i][j-1][1]-DP[i-1][j-1][1]+DP[i][j][0])%mod


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

Solution (Python):




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

MOD = 10**9+7
ls = n
lt = m

dp = [[0]*(lt+1) for _ in [0]*(ls+1)]
dp[0] = [1]*(lt+1)
for j in range(ls+1):
    dp[j][0] = 1

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] != t[j-1]:

            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] -  dp[i - 1][j - 1];
            dp[i][j] %= MOD
        else:

            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
            dp[i][j] %= MOD


print(dp[n][m])

Solution (Python):
n, m = map(int, input().split())
mod = 10 ** 9 + 7

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

arr_s = [0] + list(map(int, input().split()))
arr_t = [0] + list(map(int, input().split()))

for r in range(1, m + 1):
    for c in range(1, n + 1):
        if arr_s[c] == arr_t[r]:
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
        else:
            dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1]
        dp[r][c] %= mod

print(dp[m][n])

Solution (Python):
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 _ in range(N+1)]
for i, S in enumerate(Ss, 1):
    for j, T in enumerate(Ts, 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[-1][-1])

Solution (Python):
n,m=map(int,input().split())
s_list=[0]+list(map(int,input().split()))
t_list=[0]+list(map(int,input().split()))
dp=[]
for i in range(n+1):
    sub_list=[0]*(m+1)
    dp.append(sub_list)
for j in range(m+1):
    dp[0][j]=1
for i in range(n+1):
    dp[i][0]=1
Mod=10**9+7
for i in range(1,n+1):
    for j in range(1,m+1):
        if s_list[i]==t_list[j]:
            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):
MOD = 10**9 + 7
N,M = map(int,input().split())
S = [0] + [int(x) for x in input().split()]
T = [0] + [int(x) for x in 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):
mod = 10**9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

def CommomSubsequencesCount(s, t):

    n1 = len(s)
    n2 = len(t)
    dp = [[0 for i in range(n2 + 1)]
             for i in range(n1 + 1)]
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            if (s[i - 1] == t[j - 1]): 
                dp[i][j] = (1 + 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
    return dp[n1][n2]
ans = CommomSubsequencesCount(s, t)
ans += 1
ans %= mod
print(ans)

Solution (Python):
from functools import lru_cache
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 i,s in enumerate(S, start=1):
    ndp = [None]*(M+1)
    ndp[0] = 1
    for j,t in enumerate(T, start=1):
        if s == t:
            ndp[j] = dp[j]+ndp[j-1]
        else:
            ndp[j] = dp[j]+ndp[j-1]-dp[j-1]
    dp = ndp

print(ndp[-1]%MOD)

Solution (Python):
from itertools import accumulate
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
for i, t in enumerate(T, 1):
    dp2 = dp[:]
    for i in range(1, N+1):
        dp2[i] = (dp2[i-1] + dp2[i]) % mod
    for j, s in enumerate(S, 1):
        if s == t:
            dp[j] += dp2[j-1]
ans = 0
for d in dp:
    ans = (ans + d) % mod
print(ans)

Solution (Python):
mod = int(1e9+7)

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

dp = []
for i in range(len(s)+1):
  dp.append([0] * (len(t)+1))

for i in range(1, len(s)+1):
  for j in range(1, len(t)+1):
    if s[i-1] == t[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
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
a = [[0 for j in range(M + 1)] for i in range(N + 1)]
for i in range(N+1):
    for j in range(M+1):
        if i == 0 or j == 0:
            a[i][j] = 1
        else:
            a[i][j] = a[i-1][j] + a[i][j-1] - (a[i-1][j-1] if S[i-1] != T[j-1] else 0)
            a[i][j] %= MOD
print(a[N][M])