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 = 10**9+7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
dp[0][0] = 1
cum = [[0 for _ in range(m+1)] for _ in range(n+1)]
cum[0][0] = 1
for i in range(1, n+1):
	cum[i][0] = 1
for j in range(1, m+1):
	cum[0][j] = 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] = cum[i-1][j-1]
			dp[i][j] %= MOD
		cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + dp[i][j]
		cum[i][j] %= MOD

print(cum[n][m])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

dp = [[0] * (n+1) for _ in range(m+1)]
for i, tt in enumerate(t):
    val = 0 
    for j, ss in enumerate(s):
        # Update Partial
        if ss == tt:
            val += dp[i][j] + 1
            val %= MOD
        # Keep prev
        dp[i+1][j+1] += dp[i][j+1] + val
        dp[i+1][j+1] %= MOD 
print((dp[m][n]+1) % MOD)

Submission status: Accepted

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

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

MOD = 10**9 + 7
s = 0
rM = range(M-1, -1, -1)
for i in range(N):
    si = S[i]
    for j in rM:
        if si == T[j]:
            v = get(j+1) + 1
            add(j+2, v); s += v
print((s + 1) % MOD)

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

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

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

print(L[M][N] % 1000000007)

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=[]
for i in range(len(s)+1):
  dp.append([0]*(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[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]
print((dp[len(s)][len(t)]+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()))
dp = [1] * (M+1)
acc = [0] * (M)
MOD = 10 ** 9 + 7
for s in S:
  ndp = [1]
  for i, t in enumerate(T):
    if s == t:
      ndp.append(ndp[-1] + dp[i+1])
      acc[i] = dp[i+1]
    else:
      ndp.append(ndp[-1] + acc[i])
  dp = ndp
print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007

N, M = map(int, input().split())
S = [int(s) for s in input().split()]
T = [int(s) for s in input().split()]

m = [[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]:
            m[i][j] = m[i - 1][j] + m[i][j - 1] + 1
            m[i][j] %= MOD
        else:
            m[i][j] = m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1]
            m[i][j] %= MOD
print((m[N][M] + 1) % MOD)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))

P = 10 ** 9 + 7

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

for x in range(1, N + 1):
    for y in range(1, M + 1):
        dp[x][y] = dp[x][y - 1] + dp[x - 1][y] - dp[x - 1][y - 1]
        if S[x - 1] == T[y - 1]:
            dp[x][y] += dp[x - 1][y - 1] + 1

        dp[x][y] = dp[x][y] % P

ans = dp[N][M] + 1
print(ans % P)

Submission status: Accepted

Solution code:

def main():
    num_a, num_b = map(int, input().split())
    data_a = list(map(int, input().split()))
    data_b = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    visit_b = [0 for i in range(num_b)]

    for i in range(num_a):
        visit_b_kari = [0 for i in range(num_b)]
        now_kari = 0
        for j in range(num_b):
            if data_a[i] == data_b[j]:
                visit_b_kari[j] += now_kari + 1
                visit_b_kari[j] %= mod
            now_kari += visit_b[j]
        for j in range(num_b):
            visit_b[j] += visit_b_kari[j]
            visit_b[j] %= mod

        # print(visit_b)
        # print(visit_b_kari)

    ans = 1
    for j in range(num_b):
        ans += visit_b[j]
        ans %= mod

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
    for j in range(1, nt + 1):
        if (S[i - 1] == T[j - 1]):
            dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % MOD
        else:
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) %            MOD
print((dp[ns][nt] + 1) % MOD)

Submission status: Accepted

Solution code:

words = lambda t : list(map(t, input().split()))
n,m = words(int)
s = words(int)
t = words(int)
MOD = 10**9 + 7

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

for i in range(1,n+1):
    for j in range(1,m+1):
#        for k in range(n+1):
#            print(dp[k])
#        print("")
        if s[i-1] == t[j-1]:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]) % MOD

#for k in range(n+1):
#    print(dp[k])


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 16 22:15:18 2019

@author: Yamazaki Kenichi
"""

N, M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
mod = 10**9 + 7

A = [[1 for j in range(M+1)]]
A += [[0 for j in range(M+1)]]
#A += [[0 for j in range(M+1)] for i in range(N)]
A += [[1 for j in range(M+1)]]
for i in range(N):
#    print(i,j)
    tmp2 = 0
    for j in range(M):
#        print(i,j)
        if T[j] == S[i]:
            tmp = A[-1][j-1] % mod
#            A[i+1][j] = A[-1][j-1] % mod
        else:
            tmp = tmp2 % mod
#            A[i+1][j] = A[i+1][j-1] % mod
        tmp2 = tmp
        A[-1][j] += tmp
#        A[-1][j] += A[i+1][j]
        A[-1][j] %= mod
#        print(A)
ans = A[-1][-2] % mod
print(ans)

Submission status: Accepted

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

DP = [[0] * M for _ in range(N)]

t = 0
for i in range(M):
  if S[0] == T[i]:
    t += 1
  DP[0][i] = t

for i in range(1, N):
  cnt = 0
  while cnt < M:
    if cnt == 0:
      DP[i][0] = DP[i - 1][0]
      if S[i] == T[0]:
        DP[i][0] += 1
    else:
      if S[i] == T[cnt]:
        DP[i][cnt] = (DP[i - 1][cnt] + 1 + DP[i][cnt - 1]) % MOD
      else:
        DP[i][cnt] = (DP[i - 1][cnt] + DP[i][cnt - 1] - DP[i - 1][cnt - 1]) % MOD
      while DP[i][cnt] < MOD:
        DP[i][cnt] += MOD
    cnt += 1

print((DP[-1][-1] + 1) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    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+1][j] + dp[i][j+1] - dp[i][j]) % MOD
            if S[i] == T[j]:
                dp[i+1][j+1] += dp[i][j] + 1
            dp[i+1][j+1] %= MOD
    return (dp[-1][-1] + 1) % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, S, T)
    print(result)

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

Submission status: Accepted

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

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

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

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


for i in range(M+1):
    DP[i][0]=1

mod=10**9 + 7
for i in range(M):
    for j in range(N):
        if T[i]==S[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[M][N])

Submission status: Accepted

Solution code:
import itertools


DEF_MODULO = 10 ** 9 + 7


def solve(n, m, ss, ts, mod = DEF_MODULO):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i, j in itertools.product(range(n), range(m)):
        if ss[i] == ts[j]:
            dp[i + 1][j + 1] = 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
    return (dp[n][m] + 1) % mod


def main():
    n, m = (int(z) for z in input().split())
    ss = [int(s) for s in input().split()]
    ts = [int(t) for t in input().split()]
    res = solve(n, m, ss, ts)
    print(res)


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 = 1000000007
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(0, len(s) + 1):
    for j in range(0, len(t) + 1):
        ret = 0
        if i == 0:
            ret = 1
        elif j == 0:
            ret = 1
        else:
            ret = (dp[i][j - 1] + dp[i - 1][j]) % mod
            if s[i - 1] != t[j - 1]:
                ret = (ret + mod - dp[i - 1][j - 1]) % mod
        dp[i][j] = ret
print(dp[len(s)][len(t)])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S_list = list(map(int, input().split()))
T_list = list(map(int, input().split()))

LARGE = 10**9+7

DP = [[0]*(M+1) for _ in range(N+1)]
# DP[i][j]
# S = S[i:], T = T[j:]

for i in range(N + 1):
    DP[i][M] = 1
for j in range(M + 1):
    DP[N][j] = 1

for i in range(N - 1, -1, -1):
    for j in range(M - 1, -1, -1):
        if S_list[i] == T_list[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] = DP[i][j] % LARGE

print(DP[0][0])

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[i][j]:=Sのi字目とTのj字目までの共通部分列の数
dp=[[1 for i in range(M)] for j in range(N)]
for i in range(N):
  for j in range(M):
    if i==0:
      if j==0:
        if S[i]==T[j]:
          dp[i][j] = dp[i][j]+1
      elif S[i]==T[j]:
        dp[i][j] = (dp[i][j-1]+1)%mod
      else:
        dp[i][j] = dp[i][j-1]
    elif j==0:
      if S[i]==T[j]:
        dp[i][j] = (dp[i-1][j]+1)%mod
      else:
        dp[i][j] = dp[i-1][j]
    else:
      if S[i]!=T[j]:
        dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1])%mod
      else:
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod
print(dp[N-1][M-1]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod=10**9+7

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

DP=[[0]*(N+1) for i in range(M+1)]
#DP[0][0]=1
SUM=[[0]*(N+1) for i in range(M+1)]
SUM[0]=[1]*(N+1)
for i in range(M+1):
    SUM[i][0]=1

for j in range(1,M+1):
        
    for i in range(1,N+1):
        if S[i-1]==T[j-1]:
            DP[j][i]=SUM[j-1][i-1]

    S2=0
    for i in range(1,N+1):
        S2=(S2+DP[j][i])%mod
        SUM[j][i]=(SUM[j-1][i]+S2)%mod
    

ANS=0
for i in range(M+1):
    ANS=(ANS+sum(DP[i]))%mod

print((ANS+1)%mod)

Submission status: Accepted

Solution code:
MOD = pow(10, 9) + 7

n, m = map(int, input().split())
slist = list(map(int, input().split()))
tlist = list(map(int, input().split()))

dp = [[1 for _ in range(n+1)] for _ in range(m+1)]
for i, s in enumerate(slist):
  for j, t in enumerate(tlist):
    if s != t:
      dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD
    else:
      if slist[i] == t and tlist[j] == s:
        dp[j+1][i+1] = (dp[j+1][i] + dp[j][i+1]) % MOD
      else:
        dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

n,m = (int(num) for num in input().split())
s = [int(num) for num in input().split()]
t = [int(num) for num in input().split()]

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

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    S = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    T = list(map(int, buflist))
    dp = []
    for i in range(N+1):
        dp.append([])
        for j in range(M+1):
            dp[i].append(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__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


MOD = 1000000007


def main():
  N,M = map(int, input().split())
  Sn = list(map(int, input().split()))
  Tn = list(map(int, input().split()))

  ## dp[n][m] := Snの先頭nコ、Tnの先頭mコでの組み合わせ総数
  dp = [[1 for m in range(M+1)] for n in range(N+1)]

  for n in range(N):
    for m in range(M):
      if Sn[n]==Tn[m]:
        dp[n+1][m+1] = (dp[n][m+1]+dp[n+1][m]) % MOD
      else:
        dp[n+1][m+1] = (dp[n][m+1]+dp[n+1][m]-dp[n][m]) % MOD
  print(dp[N][M])


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()))
dp=[[1 for i in range(n+1)] for j in range(m+1)]
ans=1
mod=10**9+7
for T in range(1,m+1):
    for S in range(1,n+1):
        tmp=dp[T-1][S-1]
        if(s[S-1]==t[T-1]):
            dp[T][S]=(dp[T-1][S]+dp[T][S-1])%mod
        else:
            dp[T][S]=(dp[T-1][S]+dp[T][S-1]-tmp)%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()))
ans = 0
mod = 10**9+7
C = [1]*(N+1)
for t in T:
    d = 0
    for i, s in enumerate(S):
        d_ = C[i]
        if t==s:
            ans = (ans + d_) % mod

        C[i] += d
        C[i] %= mod
        if t==s:
            d += d_
            d %= mod
print(ans+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 = [[1 for _ in range(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] = (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

ans = dp[N][M]
print(ans)

Submission status: Accepted

Solution code:
P = 10**9+7
N, M = map(int, input().split())
S = [int(a) for a in input().split()]
T = [int(a) for a in input().split()]
X = [[1] * (M+1)] + [[1]+[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        X[i+1][j+1] = (X[i+1][j] + X[i][j+1] - (X[i][j] * (S[i] != T[j])))%P
print(X[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 = [[[0,0] for i in range(m)] for j in range(n)]

mod=10**9+7

if S[0]==T[0]:
    DP[0][0][0]=1
    DP[0][0][1]=1

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

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

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


print(DP[-1][-1][1]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


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
ls = n
lt = m

dp = [[0]*(lt+1) for _ in [0]*(ls+1)]
dp[0] = [1]*(lt+1)
for j in range(ls+1):
    dp[j][0] = 1

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] != t[j-1]:
#            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] -  dp[i - 1][j - 1];
            dp[i][j] %= MOD
        else:
#            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j] + 2*dp[i-1][j-1]
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
            dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7

dp = [[1] * (n + 1)] + [[1] + [0] * n for _ in range(m)]

arr_s = [0] + list(map(int, input().split()))
arr_t = [0] + list(map(int, input().split()))

for r in range(1, m + 1):
    for c in range(1, n + 1):
        if arr_s[c] == arr_t[r]:
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
        else:
            dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1]
        dp[r][c] %= mod

print(dp[m][n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s_list=[0]+list(map(int,input().split()))
t_list=[0]+list(map(int,input().split()))
dp=[]
for i in range(n+1):
    sub_list=[0]*(m+1)
    dp.append(sub_list)
for j in range(m+1):
    dp[0][j]=1
for i in range(n+1):
    dp[i][0]=1
Mod=10**9+7
for i in range(1,n+1):
    for j in range(1,m+1):
        if s_list[i]==t_list[j]:
            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])

Submission status: Accepted

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

def CommomSubsequencesCount(s, t):

    n1 = len(s)
    n2 = len(t)
    dp = [[0 for i in range(n2 + 1)]
             for i in range(n1 + 1)]
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            if (s[i - 1] == t[j - 1]): 
                dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % mod
            else:
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % mod
    return dp[n1][n2]
ans = CommomSubsequencesCount(s, t)
ans += 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
N,M = map(int,input().split())
S = tuple(map(int,input().split()))
T = tuple(map(int,input().split()))
MOD = 10**9 + 7

dp = [1]*(M+1)

for i,s in enumerate(S, start=1):
    ndp = [None]*(M+1)
    ndp[0] = 1
    for j,t in enumerate(T, start=1):
        if s == t:
            ndp[j] = dp[j]+ndp[j-1]
        else:
            ndp[j] = dp[j]+ndp[j-1]-dp[j-1]
    dp = ndp

print(ndp[-1]%MOD)

Submission status: Accepted

Solution code:
from itertools import accumulate
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+1)
dp[0] = 1
for i, t in enumerate(T, 1):
    dp2 = dp[:]
    for i in range(1, N+1):
        dp2[i] = (dp2[i-1] + dp2[i]) % mod
    for j, s in enumerate(S, 1):
        if s == t:
            dp[j] += dp2[j-1]
ans = 0
for d in dp:
    ans = (ans + d) % 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
a = [[0 for j in range(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:
            a[i][j] = 1
        else:
            a[i][j] = a[i-1][j] + a[i][j-1] - (a[i-1][j-1] if S[i-1] != T[j-1] else 0)
            a[i][j] %= MOD
print(a[N][M])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
S = getList()
N_s = len(S)
T = getList()
N_t = len(T)

dp = [[0] * (N_s + 1) for i in range(N_t + 1)]
dp[0][0] = 0

for i in range(N_t):
    for j in range(N_s):
        # 基礎 dp[i][j] + Sを伸ばして増えた分 + Tを伸ばして増えた分
        dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j]) % mod
        if S[i] == T[j]:
            # dp[i][j]の通りのそれぞれの末尾に(S[i], T[i])をつけることで
            # dp[i][j]通り（と空に(S[i], T[i])をつけた）分新しいのが作れる
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] + 1) % mod
print((dp[N_t][N_s] + 1) % mod)

Submission status: Runtime Error

Solution code:
from numba import njit

MOD = 10 ** 9 + 7

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

@njit
def solve(N, M, S, T):
    dp = [[1] * (M+1) for _ in range(N+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            if s != t:
                dp[i+1][j+1] -= dp[i][j]
            dp[i+1][j+1] %= MOD
    return dp[M][N]
    
print(solve(N, M, S, T))

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

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

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

print(dp[N][M])

Submission status: Runtime Error

Solution code:
import itertools
import bisect
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
ruiseki = [0]+itertools.accumulate(A)
ans = 0
for j in range(1,N+1):
    if ruiseki[i] >= K:
        ans += bisect.bisect(A,A[i]-K)
print(ans)

Submission status: Runtime Error

Solution code:
import collections as cc
import sys
#input=sys.stdin.readline
I=lambda:list(map(int,input().split()))
n,m=I()
s=I()
t=I()
l=10**6
mod=10**9+7
s.append(l)
t.append(l)
pref2d=[[0]*(m+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(m+1):
        i=i+1
        j=j+1
        if s[i]!=t[j]:
            pref2d=[i][j]=pref2d[i][j-1]+pref2d[i-1][j]-pref2d[i-1][j-1]
            pref2d%=mod
        else:
            pref2d=[i][j]=pref2d[i][j-1]+pref2d[i-1][j]+1
            pref2d%=mod
print((pref2d[n][m]+1)%mod)

Submission status: Runtime Error

Solution code:
import collections as cc
import sys
input=sys.stdin.readline
I=lambda:list(map(int,input().split()))
n,m=I()
s=I()
t=I()
l=10**6
mod=10**9+7
s.append(l)
t.append(l)
pref2d=[[0]*m+2 for i in range(n+2)]
for i in range(n+1):
    for j in range(m+1):
        i=i+1
        j=j+1
        if s[i]!=t[j]:
            pref2d=[i][j]=pref2d[i][j-1]+pref2d[i-1][j]-pref2d[i-1][j-1]
            pref2d%=mod
        else:
            pref2d=[i][j]=pref2d[i][j-1]+pref2d[i-1][j]+1
            pref2d%=mod
print((pref2d[n][m]+1)%mod)

Submission status: Runtime Error

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

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res.copy() for k in [0]*i]
    return res

dp = dpinit((N+1,M+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(1,N+1):
    s = S[i-1]
    for j in range(1,M+1):
        t = T[j-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[N][M])

Submission status: Runtime Error

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