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

sum_dp = [[0 for j in range(m+1)] for i in range(n+1)]

dp[0][0] = 1
for i,x in enumerate(S):
    for j,y in enumerate(T):
        if x == y:
            dp[i+1][j+1] = sum_dp[i][j]+1
            dp[i+1][j+1] %= mod
        else:
            dp[i+1][j+1] = 0
        sum_dp[i+1][j+1] = sum_dp[i][j+1]+sum_dp[i+1][j]-sum_dp[i][j]+dp[i+1][j+1]
        sum_dp[i+1][j+1] %= mod

ans = 0
for i in range(n+1):
    
    ans += sum(dp[i])
    ans %= mod

print(ans)

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

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

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

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
s = LI()
t = LI()
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):
        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(map(int, input().split( )))
t = list(map(int, input().split( )))

mod = 10**9 + 7

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

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

print(dp_sum[n-1][m-1]+1)

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

import numpy as np

MOD = 10**9 + 7

N,M = map(int,readline().split())
S = list(map(int,readline().split()))
T = np.array(['0']+readline().split(),np.int32)




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

for i,s in enumerate(S,1):
    prev = dp
    prev_cum = prev.cumsum() % MOD
    equal = (s == T)
    dp[1:] += equal[1:] * prev_cum[:-1]
    dp[dp>=MOD] -= MOD

answer = dp.sum() % MOD
print(answer)

Solution (Python):
n,m=map(int,input().split())
mod=10**9+7
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)]
sum=[[0 for i 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]+1)%mod
    else:dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
print((sum[-1][-1]+1)%mod)

Solution (Python):
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])

Solution (Python):
import sys
input = sys.stdin.buffer.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):
  for j in range(M):
    if S[i] == T[j]:
      dp[i + 1][j + 1] = (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[-1][-1] + 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 = [[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]*(s[i] != t[j])) % mod
print(dp[n][m])

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

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

mod = 10**9+7

dp = [[0]*m for _ in [0]*n]
a = [[0]*m for _ in [0]*n]

for i in range(n):
    a[i][0] = a[i-1][0]
    if t[0] == s[i]:
        dp[i][0] = 1
        a[i][0] += 1

for i in range(m):
    a[0][i] = a[0][i-1]
    if s[0] == t[i]:
        dp[0][i] = 1
        a[0][i] += 1

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

res = 1
for i in range(n):
    res = (res + sum(dp[i]))%mod
print(res%mod)

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

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)]
cs = [[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-1] == t[j-1]:
            dp[i][j] = 1 + cs[i-1][j-1]
            dp[i][j] %= MOD

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

print((cs[n][m] + 1) % MOD)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
s = LI()
t = LI()
dp = [[1] * (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]) % 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(map(int, input().split()))
T = list(map(int, input().split()))


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

MOD = 10 ** 9 + 7


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

Solution (Python):
import sys
from math import ceil

def input():
    return sys.stdin.readline().strip()

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def nok(a, b):
    m = a * b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a + b)    


def main():
    mod = 1e9 + 7
    n, m = rinput()
    s = rlinput()
    t = rlinput()
    a = [1] * (m + 1)
    for j in s:
        d = a[:]
        k = 0
        for i, v in enumerate(t):
            d[i] = (k + d[i]) % mod
            if j == v:
                k = (k + a[i]) % mod
        d[-1] = (k + d[-1]) % mod
        a = d[:]
    print(int(a[-1]))
    
    
    
main()

Solution (Python):
def main():
    e=enumerate
    n,m,*u=map(int,open(0).read().split())
    dp=[[1]*(m+1)for _ in range(n+1)]
    dpi=dp[0]
    for i,s in e(u[:n]):
        dpi1=dp[i+1]
        for j,t in e(u[n:]):
            dpi1[j+1]=(dpi[j+1]+dpi1[j]-dpi[j]*(s!=t))%(10**9+7)
        dpi=dpi1
    print(dpi[m])
main()

Solution (Python):
def main():
    e=enumerate
    n,m,*u=map(int,open(0).read().split())
    dp=[[1]*(m+1)for _ in range(n+1)]
    dpi=dp[0]
    for i,s in e(u[:n]):
        dpi1=dp[i+1]
        for j,t in e(u[n:]):
            dpi1[j+1]=(dpi[j+1]+dpi1[j]-dpi[j]*(s!=t))%(10**9+7)
        dpi=dpi1
    print(dpi[m])
main()

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N, M = MI()
    S = [i for i in ST().split()]
    T = [i for i in ST().split()]

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

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

if __name__ == '__main__':
    main()

Solution (Python):


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

import numpy as np
t=np.array(t,dtype=np.int64)
dp=np.ones(m+1,dtype=np.int64)

for a in s:
	dp[1:]=((dp[:-1]*(t==a)).cumsum()+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()))

MOD = 10**9+7

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


ret = 0
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            dp[i+1][j+1] = dp_sum[i][j] + 1 
        dp_sum[i+1][j+1] = (dp[i+1][j+1] + dp_sum[i][j+1] + dp_sum[i+1][j] - dp_sum[i][j]) % MOD
        
print(dp_sum[N][M]+1)

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

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

print((dp_sum[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

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

Solution (Python):
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
d = [[0 for i in range(M + 1)] for j in range(N + 1)]
mod = 1000000007

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

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
mod = 10 ** 9 + 7
sum_dp = []
for i in range(N+1):
    sum_dp.append([0] * (M+1))

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

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
mod = 10 ** 9 + 7
sum_dp = []
for i in range(N+1):
    sum_dp.append([0] * (M+1))

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

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

Solution (Python):
import sys

N,M=map(int, sys.stdin.readline().split())
S=[None]+map(int, sys.stdin.readline().split())
T=[None]+map(int, sys.stdin.readline().split())

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

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

mod=10**9+7
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]
		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]%mod

Solution (Python):
import numpy as np
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
mod = 10 ** 9 + 7
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])