Submission #5970190

---

Source Code Expand

MOD = 10**9 + 7
N,M = map(int,input().split())
S = [0] + [int(x) for x in input().split()]
T = [0] + [int(x) for x in input().split()]

# 最後に(n,m)でとる
dp = [[0] * (M+1) for _ in range(N+1)]
# 2次元累積和、(n,m) inclusive. 
dp_cum = [[0] * (M+1) for _ in range(N+1)]

# empty
dp[0][0] = 1
dp_cum[0][0] = 1
for n in range(N+1):
  dp_cum[n][0] = 1
for m in range(M+1):
  dp_cum[0][m] = 1
  
for n in range(1,N+1):
  for m in range(1,M+1):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      # (n-1, m-1)までで作れてるやつから飛んでくる
      dp[n][m] = dp_cum[n-1][m-1]
    dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + dp[n][m]
    dp_cum[n][m] %= MOD

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

Submission Info

Judge Result