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.



Sample input:
2 2
1 3
3 1


Sample output:
3

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #シンプルに！！
    
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()
    
    dp=[[0]*(M+1) for _ in range(N+1)]
    #i文字目までとj文字目まで見た．
    
    for i in range(N+1):
        dp[i][0]=1
    for j in range(M+1):
        dp[0][j]=1
    
    for i in range(N):
        for j in range(M):
            #まとめたせいで繊維が少し不自然かも
            #基本はdp[i][j]を2回数えているのでひく，でもi文字目とj文字目が一致していればたす
            dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
            if S[i]!=T[j]:
                dp[i+1][j+1]-=dp[i][j]
            dp[i+1][j+1]%=mod

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

main()

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()
    
    dp=[[0]*(M+1) for _ in range(N+1)]
    dp[0][0]=1
    #dp[i][j]はSのi文字目，Tのj文字目を使う時の通り数
    cumsum=[[0]*(M+2) for _ in range(N+2)]
    #2D累積和
    
    for i in range(1,N+2):
        cumsum[i][1]=1
    for j in range(1,M+2):
        cumsum[1][j]=1
    
    for i in range(N):
        for j in range(M):
            if S[i]==T[j]:
                dp[i+1][j+1]=(cumsum[i+1][j+1])%mod
                
            cumsum[i+2][j+2]=(cumsum[i+2][j+1]+cumsum[i+1][j+2]-cumsum[i+1][j+1]+dp[i+1][j+1])%mod
            
    print(cumsum[-1][-1])
    """
    for i in range(N+2):
        print(' '.join(map(str, cumsum[i])))
        
    for i in range(N+1):
        print(' '.join(map(str, dp[i])))"""

main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m+1) for _ in range(n+1)]

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

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

Submission status: Accepted

Solution code:
import math


class Solution:
    def solve(self, N: int, M: int, S, T):

        mod = 10**9 + 7

        N_MAX = 2005

        dp = [[0] * N_MAX for _ in range(N_MAX)]
        s = [[0] * N_MAX for _ in range(N_MAX)]

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

        return (s[N][M] + 1)


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    # solve
    solution = Solution()
    print(solution.solve(N, M, S, T))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
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 range(n+1)]
    for si in range(1, n+1):
        for ti in range(1, m+1):
            if s[si-1] == t[ti-1]:
                dp[si][ti] += 1
                dp[si][ti] += dp[si-1][ti-1]
            dp[si][ti] += dp[si-1][ti] + dp[si][ti-1]
            dp[si][ti] -= dp[si-1][ti-1]
            dp[si][ti] %= MOD
    print(dp[n][m] + 1)
#    for i in range(n+1):
#        print(dp[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
    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 i, S in enumerate(Ss, 1):
        dp2 = [1]*(M+1)
        for j, T in enumerate(Ts, 1):
            dp2[j] = dp[j] + dp2[j-1]
            if S != T:
                dp2[j] -= dp[j-1]
            dp2[j] %= MOD
        dp = dp2

    print(dp[-1])


solve()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

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

Submission status: Accepted

Solution code:
# 解説AC
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[i][j]: S[:i]とT[:j]の共通部分列のうち、
# S[i - 1] == T[j - 1]で、これを選ぶ場合の個数
dp = [[0] * (M + 1) for _ in range(N + 1)]

# DPの二次元累積和
sdp = [[0] * (M + 1) for _ in range(N + 1)]

# 初期条件
dp[0][0] = 1
for i in range(N + 1):
    sdp[i][0] = 1
for j in range(M + 1):
    sdp[0][j] = 1

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

print(sdp[N][M])

Submission status: Accepted

Solution code:
# 解説AC
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[i][j]: S[:i]とT[:j]での共通部分列の個数
dp = [[0] * (M + 1) for _ in range(N + 1)]

def main():
    # 初期条件
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    # 貰うDP
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]

            if s == t:
                dp[i + 1][j + 1] += dp[i][j]
            
            # ダブルカウントを除く
            dp[i + 1][j + 1] -= dp[i][j]

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

    print(dp[N][M])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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 = [[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]) % mod
        if S[i-1] == T[j-1]:
            dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod
print(dp[N][M])

Submission status: Accepted

Solution code:


def resolve():
    MOD = int(1e9+7)
    N,M = map(int,input().split())
    S= list(map(int,input().split()))
    T= list(map(int,input().split()))
    dpt = [[0]*(M+1) for i in range(N+1)]

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

    for i in range(N):
        for j in range(M):
            dpt[i+1][j+1]= sm[i][j]+1 if S[i]==T[j] else 0

            sm[i+1][j+1] = (sm[i][j+1]+sm[i+1][j]+dpt[i+1][j+1]-sm[i][j]+MOD)%MOD
    ans =0
    for dptr in dpt:
        for i in dptr:
            ans += i
            ans %= MOD

    print(ans+1)            



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
PR = 1000000007

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):
		#aa
		sumI = 0
		sumI = dp[i+1][j]
#		for jj in range(0,j):
#			if s[i] == t[jj]:
#				sumI=(sumI + dp[i][jj]) % PR
		
		sumJ = 0
		sumJ = dp[i][j+1]
#		for ii in range(0,i):
#			if t[j] == s[ii]:
#				sumJ=(sumJ + dp[ii][j]) % PR
		
		if s[i] == t[j]:
			dp[i+1][j+1] = (sumI + sumJ) % PR
		else:
			dp[i+1][j+1] = (sumI + sumJ - dp[i][j]) % PR
#		print("i: %d j: %d  sumI: %d sumJ:%d dp[i][j]:%d" % (i+1,j+1,sumI,sumJ,dp[i+1][j+1]))

#print(dp)
print(dp[n][m])

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
S = tuple(map(int, input().split()))
T = np.array(input().split(), np.int64)
mod = 10 ** 9 + 7

dp = np.ones(M + 1, np.int64)
for i in S:
    tmp = (T == i)
    dp[1:] = (np.cumsum(tmp * dp[:-1]) + dp[1:]) % mod

print(dp[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp0 = [[0 for i in range(m+2)] for j in range(n+2)]
dp1 = [[0 for i in range(m+2)] for j in range(n+2)]
dp0[0][0] = 1
mod = 10**9+7
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] = (dp0[i+1][j]+dp0[i][j])%mod
        dp1[i][j] = (dp1[i][j]+dp0[i][j])%mod
        dp1[i][j+1] = (dp1[i][j+1]+dp1[i][j])%mod
        if i != n and j != m and s[i] == t[j]:
            dp0[i+1][j+1] = (dp1[i+1][j+1]+dp1[i][j])%mod
print(dp1[n][m])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    MOD = 10**9+7
    
    num = [[0 for _ in range(M+1)] for _ in range(N+1)]
    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

    ans = 1
    for i in range(N):
        for j in range(M):
            if s[i] == t[j]:
                num[i+1][j+1] = (dp[i][j])%MOD
                ans += num[i+1][j+1]
            dp[i+1][j+1] = (dp[i][j+1]+dp[i+1][j]-dp[i][j]+num[i+1][j+1])%MOD
    
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
    dp[i][0] = 1
for j in range(m + 1):
    dp[0][j] = 1

for i, es in enumerate(s, 1):
    for j, et in enumerate(t, 1):
        dp[i][j] += dp[i-1][j]
        dp[i][j] += dp[i][j-1]
        dp[i][j] -= dp[i-1][j-1]
        if es == et:
            dp[i][j] += dp[i-1][j-1]

        dp[i][j] %= mod

ans = dp[n][m]
print(ans)

Submission status: Accepted

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

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

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

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

print(dp[N-1][M-1]%(10**9+7))

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
S = ['?'] + lr()
T = ['.'] +lr()
# dp[i][j] はSがi文字目までTがj文字目までの部分列で等しい組の総和
dp = [[1] * (M+1) for _ in range(N+1)]

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

answer = dp[N][M]
print(answer%MOD)
# 21 pypy

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)

Submission status: Accepted

Solution code:
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] = (dp[i][j+1] + dp[i+1][j] + 1) % mod
        else:
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % mod

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

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
S = [0] + lr()
T = [0] + lr()
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 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(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = dp_cum[i-1][j-1]
        else:
            dp[i][j] = 0
        dp_cum[i][j] = (dp_cum[i-1][j] + dp_cum[i][j-1] - dp_cum[i-1][j-1] + dp[i][j]) % MOD

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

Submission status: Accepted

Solution code:
MOD = 1000000007

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,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]
        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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#15:35
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)
print(now[-1])

Submission status: Accepted

Solution code:
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
#import numpy as np
#import sympy as syp(素因数分解とか)
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(): #startline--------------------------------------------
    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() 
    
#endline===============================================

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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(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)
# print(*arr,sep="\n");print()
# print(*acum,sep="\n")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)
# print(*arr,sep="\n");print()
# print(*acum,sep="\n")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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