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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)] # dp の累積和を持つ
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split()) #<=2*10**3
#n
s=list(map(int,input().split()))
#m
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %=mod
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC130 E

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

n,m = LI()
s = LI()
t = LI()
dp  = [[0]*(m+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n+1):
    dp[i][0] = 1
for j in range(m+1):
    dp[0][j] = 1
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % mod
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]) % mod
print(dp[n][m])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

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

# Sは左から見ていく。
# Tについて、（最後に一致させた文字の位置、通り数）をdpで持つ

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
  for j in range(M):
    if S[i] == T[j]:
      dp[i + 1][j + 1] = (1 + dp[i + 1][j] + dp[i][j + 1]) % mod
    else:
      dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j]) % mod
print((dp[-1][-1] + 1) % mod)

Submission status: Accepted

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

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

mod = 10**9+7

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

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

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

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

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

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

Submission status: Accepted

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


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


n, m = LI()
s = LI()
t = LI()
dp = [[1] * (m + 1) for _ in range(n + 1)]


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



print(dp[n][m])

Submission status: Accepted

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

# dp[i][j] : Sのi-1文字目、Tのj-1文字目までの解(文字目は0-index)
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
#print(dp)
MOD = 10 ** 9 + 7

# なぜこれでよいのかわからない。。。
for i in range(1,N+1):
  for j in range(1,M+1):
    if S[i-1] == T[j-1]:
      # Sのi-1文字目、Tのj-1文字目が一致している場合は、
      # Sのi-2文字目、Tのj-2文字目までの部分列それぞれ
      # Sのi-1文字目、Tのj-1文字目を追加したものと、
      # Sのi-1文字目だけ、Tのj-1文字目だけの部分列パターンが
      # 増えるということだろうか。
      # つまり
      # dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + (dp[i-1][j-1] + 1)
      #            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      #            ここはS[i-1] != T[j-1]のときと同じ。
      # ということか？
      dp[i][j] = dp[i][j-1] + dp[i-1][j] + 1
    else:
      # dp[i-1][j-1]を引いているのは重複部分の排除？
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
    #print(i,j,dp[i][j],dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
    dp[i][j] %= MOD
print(dp[N][M]+1) #1を足しているのは部分列()の分をカウントするため？

Submission status: Accepted

Solution code:
import sys
from math import ceil

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

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

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

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

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

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

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

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

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

    dp = [[ModInt(1)] * (M + 1) for _ in range(N + 1)] #dp[i][j]:=i,j文字目までの整数列組数

    for i,s in enumerate(S,start = 1):
        for j,t in enumerate(T,start = 1):
            if t == s:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

for a in s:
	dp[1:]=((dp[:-1]*(t==a)).cumsum()+dp[1:])%mod
print(dp[-1])

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 i in range(M+1)] for j in range(N+1)] # dp[i][j] : S[i]とT[j]が末尾に来る部分集合の数
dp_sum = [[0 for i in range(M+1)] for j in range(N+1)] # dp[i][j]の総和

# 一旦空集合＋空集合は考えない
ret = 0
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            dp[i+1][j+1] = dp_sum[i][j] + 1 # S[i]とT[j]を使ってないものの総和にS[i]とT[j]だけの組み合わせを足す
        dp_sum[i+1][j+1] = (dp[i+1][j+1] + dp_sum[i][j+1] + dp_sum[i+1][j] - dp_sum[i][j]) % MOD
        
print(dp_sum[N][M]+1)#最後に空集合＋空集合を加える

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
import sys

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

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

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

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

print dp[-1][-1]%mod

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
mod = 10 ** 9 + 7
dp = np.ones(M + 1, dtype = np.int64)
 
for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % mod

print(dp[M])