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 = (int(i) for i in input().split())
MOD = 10**9 + 7
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]

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

Solution (Python):
def solve():
    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):
            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__':
    solve()

Solution (Python):
from collections import defaultdict
import bisect
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9+7
p = max(n,m)
if n>m:
  t.extend((0,)*(n-m))
else:
  s.extend((0,)*(m-n))
dp = [[1 for i in range(p+1)] for j in range(p+1)]
for i in range(1,p+1):
  for j in range(1,p+1):
    x = s[i-1]
    y = t[j-1]
    if x == y:
      dp[i][j] = (dp[i-1][j]+dp[i][j-1])%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):

h,w = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
mod = 10 ** 9 + 7
now = [1 for _ in range(w+1)]
for i in range(h):
  last = now
  now = [1]
  for j in range(w):
    if a[i] == b[j]:
      now.append((last[j+1]+now[-1])%mod)
    else:
      now.append((last[j+1]+now[-1]-last[j])%mod)
  
print(now[-1])

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    dp = [[0]*(m+2) for i in range(n+2)]
    sdp = [[0]*(m+2) for i in range(n+2)]
    dp[0][0] = 1
    sdp[1][1] = 1
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 and j == 0:continue
            if i>=1 and j >= 1 and s[i-1] == t[j-1]:
                dp[i][j] = sdp[i][j]%Mod
            sdp[i+1][j+1] = (sdp[i+1][j] + sdp[i][j+1] - sdp[i][j] + dp[i][j])%Mod

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

print((dp[N][M] + 1) % 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()))

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

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

print(sm[N][M])

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
sm = [[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] = (sm[i - 1][j - 1] + 1) % MOD
        else:
            dp[i][j] = 0
        sm[i][j] = (sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1] + dp[i][j]) % MOD

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

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
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', '')

def main():
    N,M=MI()
    *S,=ST().split()
    *T,=ST().split()

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

M = 10**9+7

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]
    else:
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
    dp[i+1][j+1] %= M


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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
arr=[[0]*m for i in range(n)]
for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            arr[i][j] = 1
acum = [[0]*m for i in range(n)]
acum[0][0] = arr[0][0]




for i in range(n):
    for j in range(m):
        arr[i][j] += ((acum[i-1][j-1])*(arr[i][j]) if i-1 >= 0 and j-1 >= 0 else 0)
        acum[i][j] = (acum[i-1][j] if i-1>=0 else 0) + (acum[i][j-1] if j-1>=0 else 0) - (acum[i-1][j-1]if i-1>=0 and j-1 >=0 else 0) + arr[i][j]
        arr[i][j] %= mod; acum[i][j] %= mod
print(1+sum(map(sum,arr))%mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
arr=[[0]*m for i in range(n)]
for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            arr[i][j] = 1
acum = [[0]*m for i in range(n)]
acum[0][0] = arr[0][0]
for i in range(1,n):
    acum[i][0] = acum[i-1][0] + arr[i][0]
for j in range(1,m):
    acum[0][j] = acum[0][j-1] + arr[0][j]
for i in range(1,n):
    for j in range(1,m):
        arr[i][j] += (acum[i-1][j-1])*(arr[i][j])
        acum[i][j] = acum[i-1][j] + acum[i][j-1] - acum[i-1][j-1] + arr[i][j]
        arr[i][j] %= mod; acum[i][j] %= mod
print(1+sum(map(sum,arr))%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] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      
    if j > 0:
      dp[i][j] += dp[i][j-1]

    if si == tj:
      dp[i][j] += 1
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
    
    dp[i][j] %= MOD

print((dp[n-1][m-1] + 1) % MOD)

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = tuple(map(int, input().split()))
    T = tuple(map(int, input().split()))
    l = [[0] * (M + 1) for _ in range(N + 1)]
    l[0] = [1] * (M + 1)
    for i in range(N + 1):
        l[i][0] = 1
    r = 1
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i-1] == T[j-1]:
                r += l[i-1][j-1]
                l[i][j] = l[i][j-1] + l[i-1][j]
                l[i][j] %= MOD
            else:
                l[i][j] = l[i][j-1] + l[i-1][j] - l[i-1][j-1]
        r %= MOD
    print(r % MOD)
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)]
mod = 10 ** 9 + 7
for si in s:
    memo = [0]
    for i, ti in enumerate(t):
        memo.append((memo[-1] + dp[i]) % mod)
    for i, ti in enumerate(t):
        if si == ti:
            dp[i] += memo[i] + 1
            dp[i] %= mod

ans = 1
for dpi in dp:
    ans += dpi
    ans %= mod
print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split())) + [0]
    T = list(map(int, input().split())) + [0]
    dp0 = [[0] * (M + 5) for _ in range(N + 5)]
    dp1 = [[0] * (M + 5) for _ in range(N + 5)]
    MOD = 10 ** 9 + 7
    dp0[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            dp0[i+1][j] += dp0[i][j]
            dp0[i+1][j] %= MOD
            dp1[i][j] += dp0[i][j]
            dp1[i][j] %= MOD
            dp1[i][j+1] += dp1[i][j]
            dp1[i][j+1] %= MOD
            if S[i] == T[j]:
                dp0[i+1][j+1] += dp1[i][j]
                dp0[i+1][j+1] %= MOD

    ans = dp1[N][M] % MOD
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
p=[0]*m
for s in S:
  k=0
  d=[0]*(m+1)
  for i in range(m):
    if T[i]==s:
      k+=p[i-1]+1
    d[i]=(p[i]+k)%(10**9+7)
  p=d
print(p[-2]+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
for s in S:
    k=0
    d = [0]*(m+1)
    for i in range(m):
        if T[i]==s:
            k+=dp[i-1]+1
        d[i]=(dp[i]+k)%mod
    dp=d
print(dp[-2]+1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[1 if i==j else 0 for j in t] for i in s]
    u = [0] * m
    for i in range(n):
        c = a[i]

        for j in range(1,m):
            if c[j] == 1:
                c[j] += u[j-1]

        e = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod

        if i > 0:
            for j in range(m):
                e[j] += u[j]
                e[j] %= mod
        u = e

    r = sum(map(lambda x: sum(x) % mod, a)) + 1

    return r % mod


print(main())

Solution (Python):

N,M = map(int,input().split())

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


ans = [[0] * (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:
            ans[i][j] = 1

        elif S[i-1] == T[j-1]:
            ans[i][j] = ans[i-1][j] + ans[i][j-1]

        else:
            ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1]

        ans[i][j] %= (10 ** 9 + 7)

print (ans[-1][-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)]
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-1]==t[j-1]: dp[i][j]=sum[i-1][j-1]+1
    sum[i][j] = (sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+dp[i][j]+mod)%mod
ans=1
for d in dp: 
  for x in d: ans+=x
print(ans%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)]

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

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

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

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

Solution (Python):
mod=1e9+7
import sys
input=sys.stdin.readline

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    sum=[[0 for i in range(M+1)] for j in range(N+1)]
    dp=[[0 for i in range(M+1)] for j in range(N+1)]

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


    ans=sum[N][M]+1
    print(int(ans))

Solution (Python):
from numpy import array, ones

mod = 10 ** 9 + 7

N, M, *ST = map(int, open(0).read().split())
S, T = ST[:N], array(ST[N:])

dp = ones(M + 1, dtype="int64")
for s in S:
    dp[1:] = ((dp[:-1] * (s == T)).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]*(m+1) for i in range(n+1)]
for si in range(n+1):
    dp[si][0] = 1
for ti in range(m+1):
    dp[0][ti] = 1

for si in range(n):
    for ti in range(m):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = dp[si][ti+1] + dp[si+1][ti]
            dp[si+1][ti+1] %= MOD 
        else:
            dp[si+1][ti+1] = dp[si][ti+1] + dp[si+1][ti] - dp[si][ti] 
            dp[si+1][ti+1] %= MOD

print(dp[-1][-1] % 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]*(len(T)+1) for _ in range(len(S)+1)]
for s in range(len(S)+1):
    for t in range(len(T)+1):
        if s == 0 or t == 0:
            dp[s][t] = 1

for s in range(len(S)):
    for t in range(len(T)):
        if S[s]==T[t]:
            dp[s+1][t+1] = (dp[s+1][t]+dp[s][t+1])%mod
        else:
            dp[s+1][t+1] = (dp[s+1][t]+dp[s][t+1]-dp[s][t])%mod
print(dp[len(S)][len(T)])

Solution (Python):
def f():
    import sys
    input=sys.stdin.readline
    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
    dp=[[0]*(m+1) for i in range(2)]
    dp[0][0]=1
    for i in range(n+1):
        for j in range(m+1):
            if i!=0:
                dp[i%2][j]=dp[(i-1)%2][j]
            if j!=0:
                dp[i%2][j]+=dp[i%2][j-1]
            if i!=0 and j!=0:
                if s[i-1]!=t[j-1]:
                    dp[i%2][j]-=dp[(i-1)%2][j-1]
            dp[i%2][j]%=mod
    print(dp[n%2][m])


f()

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

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

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

ans = DP[m-1][n-1] + 1
print(ans)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    C=[[0]*(m+1) for _ in range(n+1)] 
    for i in range(n): C[i][0]=1
    for j in range(m): C[0][j]=1

    for i in range(n):
        for j in range(m):
            if(S[i]==T[j]): C[i+1][j+1]+=C[i][j]
            C[i+1][j+1]+=C[i+1][j]+C[i][j+1]-C[i][j]
            C[i+1][j+1]%=MOD

    print((C[-1][-1]+2)%MOD)
resolve()

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

    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]
            dp1[i][j] += dp0[i][j]
            dp1[i][j] %= MOD
            dp1[i][j + 1] += dp1[i][j]
            if i < N and j < M and S[i] == T[j]:
                dp0[i + 1][j + 1] += dp1[i][j]
            dp1[i][j] %= MOD
            dp0[i + 1][j] %= MOD
            dp1[i][j + 1] %= MOD
            dp0[i + 1][j + 1] %= MOD

    ans = dp1[N][M] % MOD
    print (ans)
    return 

if __name__ == '__main__':
    main()

Solution (Python):
MOD=1000000007
n,m=map(int,input().split())

S=[int(_) for _ in input().split()]
T=[int(_) for _ in 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]-dp[i][j]
            dp[i+1][j+1]%=MOD
        else:
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
            dp[i+1][j+1]%=MOD
print((dp[n][m])%MOD)

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

Solution (Python):
import numpy as np
N, M = map(int, input().split())
MOD = 10**9+7
s = np.array([int(c) for c in input().split()], dtype=np.int32)
t = np.array([int(c) for c in input().split()], dtype=np.int32)
dp = np.zeros((N+1,M+1), np.int64)
dp[0] = 1
for i in range(N):
  mask = s[i]==t
  dp[i+1,1:][mask] = dp[i,:-1][mask]
  dp[i+1] = (np.cumsum(dp[i+1])+dp[i])%MOD
print(dp[-1,-1])

Solution (Python):


import sys
input=sys.stdin.readline

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

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

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

Solution (Python):
import numpy as np
MOD = 10**9+7
N, M = map(int, input().split())
s = np.array(input().split(), dtype=np.int32)
t = np.array(input().split(), dtype=np.int32)

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

for i in range(N):
  same = (s[i]==t)
  dp[i+1,1:][same] = dp[i,:-1][same]
  dp[i+1] = (dp[i+1].cumsum()+dp[i])%MOD

print(dp[-1,-1])

Solution (Python):
N, M = map(int, input().split())
s = [int(c) for c in input().split()]
t = [int(c) for c in input().split()]
MOD = 10**9+7

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

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

print(dp_cum[-1][-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 _ 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
for i in range(N):
    for j in range(M):
        flg = 0 if S[i] == T[j] else 1
        dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j] * flg)%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()))
mod=10**9+7
ans=[0]*m

for u in s:
    h=[0]*m
    if u==t[0]:
        h[0]=1
    for i in range(1,m):
        if t[i]==u:
            h[i]+=ans[i-1]+1
        h[i]+=h[i-1]
    for i in range(m):
        ans[i]=(ans[i]+h[i])%mod
print((ans[-1]+1)%mod)

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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    C=[[0]*(m+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(range(n),range(m)):
        dp=C[i][j]+1 if(S[i]==T[j]) else 0
        C[i+1][j+1]=dp+C[i][j+1]+C[i+1][j]-C[i][j]
        C[i+1][j+1]%=MOD
    print(C[n][m]+1)
resolve()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i - 1][j] + sumdp[i][j - 1] +1

        
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %=mod




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

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

Solution (Python):
import itertools
N, M = [int(_) for _ in input().split()]
S = [int(_) for _ in input().split()]
T = [int(_) for _ in input().split()]
mod = 10**9 + 7
dp = [[1] * (M + 1)] + [[1] + [0] * M for _ in range(N)]
for n, m in itertools.product(range(N), range(M)):
    dp[n + 1][m + 1] = dp[n][m + 1] + dp[n + 1][m] - dp[n][m]
    if S[n] == T[m]:
        dp[n + 1][m + 1] += dp[n][m]
    dp[n + 1][m + 1] %= mod
print(dp[-1][-1])

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

N, M = map(int, input().split())
S = input().split()
T = 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 1 <= i and 1 <= j and S[i - 1] == T[j - 1]:
            dp[i][j] += dp[i - 1][j - 1]
        if 1 <= i:
            dp[i][j] += dp[i - 1][j]
        if 1 <= j:
            dp[i][j] += dp[i][j - 1]
        if 1 <= i and 1 <= j:
            dp[i][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()))
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 x in dp:
    ans += sum(x)
    ans %= mod

print(ans)