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



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""




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

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

dp[0][0] = 1
dp_sum[0][0] = 1

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

print(dp_sum[N][M])

"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""




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

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

dp[0][0] = 1
dp_sum[0][0] = 1

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

print(dp_sum[N][M])

"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

Solution (Python):
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
dp = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp[0] = [1]*(len(T)+1)
dp_sum = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp_sum[0] = [1]*(len(T)+1)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp_sum[i][j]
        dp_sum[i+1][j+1] = (dp[i+1][j+1]+dp_sum[i+1][j]+\
            dp_sum[i][j+1]-dp_sum[i][j])%(10**9+7)
print(dp_sum[-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)] for _ in range(n)]
sd = [[0 for _ in range(m)] for _ in range(n)]

ans = 1

if s[0] == t[0]:
    dp[0][0] = 1
    sd[0][0] = 1
    ans += 1

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

for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
        ans += 1
    sd[0][j] = dp[0][j] + sd[0][j-1]

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

print(ans)

Solution (Python):
mo=10**9+7
n,m=map(int,input().split())
s=[0]+[int(i) for i in input().split()]
t=[0]+[int(i) for i in input().split()]
dp=[[0]*(1+n) for i in range(1+m)]
sm=[[0]*(1+n) for i in range(1+m)]

for i in range(1,1+m):
    if t[i]==s[1]:
        dp[i][1]=1
    sm[i][1]=sm[i-1][1]+dp[i][1]%mo

for i in range(1,1+n):
    if s[i]==t[1]:
        dp[1][i]=1
    sm[1][i]=sm[1][i-1]+dp[1][i]%mo

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

print(1+sm[m][n]%mo)

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

Solution (Python):
D = 10**9+7
N, M = list(map(int,raw_input().split()))
S = list(map(int,raw_input().split()))
T = list(map(int,raw_input().split()))
a = [[0 for j in xrange(M+1)] for i in xrange(N+1)]
for i in xrange(N+1):
  a[i][0] = 1
for j in xrange(M+1):
  a[0][j] = 1
for i in xrange(N):
  for j in xrange(M):
    a[i+1][j+1] = (a[i][j+1]+a[i+1][j])%D
    if S[i]!=T[j]:
      a[i+1][j+1] = (a[i+1][j+1]-a[i][j])%D
print(a[N][M])

Solution (Python):
import numpy as np

N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = np.array(list(map(int, input().split())))

dp = np.ones(M+1, dtype='int64')

for s in S:
    dp[1:] = ((dp[:-1] * (s == T)).cumsum() + dp[1:]) % (10**9+7)
print(dp[-1])

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

A = []
B = []
mod = 10**9 + 7

for i in range(N):
    if S[i] in T:
        A.append(S[i])

for i in range(M):
    if T[i] in S:
        B.append(T[i])        
        
l1 = [1] * (N + 1)

for i, t in enumerate(T):
    l2 = l1[:]
    k = 0
    for j, s in enumerate(S):
        if t == s:
            k += l1[j]
        l2[j + 1] = (l1[j + 1] + k) % mod
    l1 = l2
print(l1[-1])

Solution (Python):
N,M = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]

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

mod = 1000000007
for n in range(N):
    for m in range(M):
        if S_arr[n] == T_arr[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]) % mod
        else:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]-dp[n][m]) % 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 = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = (ndp[m] + dp[m+1]) % MOD
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = (ndp[m] + dpleft[m]) % MOD
        dp[m] = ndp[m]
    dp[-1] = ndp[-1]
print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
        dp[m] = ndp[m]
    dp[M] = ndp[M]
print(dp[-1] % MOD)

Solution (Python):
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)

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

Solution (Python):
DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

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

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

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

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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 + 1):
	for j in range(M + 1):
		if i == 0 or j == 0:
			dp[i][j] = 1
		elif 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):
import sys

def main():
    input = sys.stdin.readline
    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)]
    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] == T[j]:
                dp[i][j] += dp[i-1][j-1] + 1
            dp[i][j] %= MOD

    return (dp[N][M] + 1) % MOD


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

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    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)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i] == T[j]:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            dp[i][j] %= MOD

    return (dp[N][M] + 1) % MOD


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

Solution (Python):
N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1









for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])

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 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] = (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[-1][-1] + 1) % mod)

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

print((dp[n][m]+1)%mod)

Solution (Python):

import sys
INF = float("inf")
MOD = 1000000007  


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for j in range(1, M+1):
        for i in range(1, N+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    
    print(DP[M][N])


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
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle




sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7






def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                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()))
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)]

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

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

print(ans % MOD)

Solution (Python):


N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        if S[i] != T[j]:
            total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        else:
            total[I][J] = (total[I][J-1] + total[I-1][J] + 1) % MOD
        
print((total[N][M] + 1) % MOD)

Solution (Python):


N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
dp = [[0 for j in range(M+2)] for i in range(N+2)]
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        if S[i] != T[j]:
            continue
        
        dp[I][J] = total[I-1][J-1] + 1
        total[I][J] = (total[I][J] +  dp[I][J]) % MOD
print(dp[N+1][M+1])

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

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

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

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

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

print((ans + 1) % MOD)

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

print((dp[n][m]+1)%mod)

Solution (Python):


def main():

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

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

if __name__ == '__main__':
    main()

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

def main():

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

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

if __name__ == '__main__':
    main()

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


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

Solution (Python):

import sys
INF = float("inf")
MOD = 1000000007  


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    
    print(DP[M][N])


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