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: Runtime Error

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: Runtime Error

Solution code:
from functools import lru_cache
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)] for _ in range(n)]
@lru_cache(None)
def solve(i,j):
    if i==0 and j==0:
        if s[i]==t[j]:
            return 1
        else:
            return 0
    if i<0 or j<0:
        return 0
    ret=0
    ret=solve(i-1,j)+solve(i,j-1)-solve(i-1,j-1)
    ret%=mod
    if s[i]==t[j]:
        ret+=1+solve(i-1,j-1)
    return ret%mod
print((solve(n-1,m-1)+1)%mod)

Submission status: Runtime Error

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

memo = [[0] * M for _ in range(N)]
def dfs(i, j):
    if i < 0 or j < 0:
        return 1
    if memo[i][j] != 0:
        return memo[i][j]
    if S[i] == T[j]:
        memo[i][j] = (dfs(i-1, j) + dfs(i, j-1)) % mod
    else:
        memo[i][j] = (dfs(i-1, j) + dfs(i, j-1) - dfs(i-1, j-1)) % mod
    return memo[i][j]

print(dfs(N-1, M-1))

Submission status: Runtime Error

Solution code:
import sys
import bisect
from functools import lru_cache
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

if N < M:
    N, M = M, N
    S, T = T, S

idxs = {}
for n in range(10):
    arr = [i for i, x in enumerate(S) if x == n]
    idxs[n] = arr


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    t_idxs = idxs[t]
    l = bisect.bisect_left(t_idxs, i)
    # print(idxs)

    for idx in t_idxs[l:]:
        ans += solve(idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)

Submission status: Runtime Error

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]*(n+2) for i in range(m+2)]
    sdp = [[0]*(n+2) for i in range(m+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]
            sdp[i+1][j+1] = sdp[i+1][j] + sdp[i][j+1] - sdp[i][j] + dp[i][j]

    print(sdp[n+1][m+1]%Mod)

if __name__ == "__main__":
    main() 
    
#endline===============================================

Submission status: Runtime Error

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

dp0 = [[0]*(N+5) for _ in range(M+5)]  # i方向に進める
dp1 = [[0]*(N+5) for _ in range(M+5)]  # j方向に進める
dp0[0][0] = 1

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 S[i] == T[j]:
            dp0[i + 1][j + 1] = (dp0[i + 1][j + 1] + dp1[i][j]) % mod

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

Submission status: Runtime Error

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

from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)

    lcm = reduce(lcm_base, a, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
mod=1e9+7

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    dp=[[0 for i in range(M+1)] for j 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(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j]+dp[i ][j + 1]-dp[i][j]
            if S[i]==T[j]:
                dp[i+1][j+1]+=dp[i][j]

    print(int(dp[N][M]%mod))

Submission status: Runtime Error

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: Runtime Error

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] * (N + 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: Runtime Error

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=[[0 for i in range(n+1)] for i in range(m+1)]
sum=[[0 for i in range(n+1)] for i 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]=(sum[i-1][j-1]+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[-1][-1]%mod)

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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

res = [[-1 for _ in range(M)] for _ in range(N)]
dpl = [[-1 for _ in range(M)] for _ in range(N)]
def dp(i, j):
  if i < 0:
    return 0
  if j < 0:
    return 0
  if dpl[i][j] != -1:
    return dpl[i][j]
  if i == 1:
    temp = 0
    for k in range(j):
      temp += S[i] == T[k]
    return temp
  elif j == 1:
    temp = 0
    for k in range(j):
      temp += S[k] == T[j]
    return temp
  temp = 0
  for k in range(i):
    for l in range(j):
      temp += dpl[k][l]
      
  return temp

def search(i, j):
  if i < 0:
    return 0
  if j < 0:
    return 0
  if res[i][j] != -1:
    return res[i][j]
  temp = 0
  if S[i] == T[j]:
    temp = 1
    temp += dp[i][j]
  else:
    temp = 0
  return search(i - 1, j) + search(i, j - 1) - search(i - 1, j - 1) + temp

print(search(N - 1, M - 1) % mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
T = list(map(int, input().split()))
mod=10**9+7
if n<m:
    aa=m
    m=n
    n=aa

dp=[0]*m 
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if s[i]==T[j]:
            dp[j]=1
            if j>0:
                dp[j]+=buf[t][j-1]
            count+=dp[j]
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        if j>0:
            buf[1-t][j]+=(buf[1-t][j-1]-buf[t][j-1])
print((count+1)%mod)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

dp = arr = [[0 for i in range(N+1)] for j in range(M+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):
        if 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]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

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

Submission status: Runtime Error

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
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 = []  # prime factor
    b, e = 2, 0  # base, exponent
    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
    """
    # TODO: How should I do when n - r is negative?
    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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
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 # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
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
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
sys.stdin = open('sample.txt') # for test

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

dp = [[0]*(M+1) for _ in range(N+1)] #dp[N][M]
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
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""


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

Submission status: Runtime Error

Solution code:
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(dpleft)
print(dp[-1] % MOD)

Submission status: Runtime Error

Solution code:
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):
    #ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            #ndp.append(ndp[-1] + dp[m+1])
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
            #ndp.append(ndp[m] + dpleft[m])
    dp = ndp[:]
    print(dpleft)
print(dp[-1] % MOD)

Submission status: Runtime Error

Solution code:
import copy
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):
    #ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            #ndp.append(ndp[-1] + dp[m+1])
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
            #ndp.append(ndp[m] + dpleft[m])
    dp = copy.deepcopy(ndp)
    print(dpleft)
print(dp[-1] % MOD)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

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

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

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

    if S[0] == S[1] and S[1] == 1 and T[0] == T[1] and T[1] == 1:
        hogehoge
        pass

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

# Sのi文字目までと、Tのj文字目までで、dp[i][j]こ
dp = [[0]*(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] = 1+dp[i-1][j]+dp[i][j-1]
            dp[i][j] %= MOD
        else:
            dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            dp[i][j] %= MOD
print((dp[-1][-1]+1) % MOD)

Submission status: Runtime Error

Solution code:
MOD = 1000000007
n, m = list(map(int, input.split()))
a = list(map(int, input.split()))
b = list(map(int, input.split()))
f = [[0] * (m + 1)]
for i in range(n):
  f.append([0] * (m + 1))
for i in range(1, n + 1):
  for j in range(1, m + 1):
    f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MOD
    if a[i - 1] != b[j - 1]:
      f[i][j] = (f[i][j] + MOD - f[i - 1][j - 1]) % MOD
print(f[n][m])

Submission status: Runtime Error

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

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

dp = np.zeros((N, M), dtype=int)
dp_sum = np.zeros((N + 1, M + 1), dtype=int)

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

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=[1]*(m+1)
for i in range(n):
    b=a[:]
    k=0
    for j in range(m):
        b[j]=(k+b[j])%(10**9+7)
        if s[i]==t[j]:
            k=(k+a[j])%(10**9+7)
    b[-1]=(k+b[-1])%(10**9+7)
    a=b[:]
print(a[-1]%(10**9+7))
~

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp=[[0 for j in range(M)] for i in range(N)]

for i in range(N):
	for j in range(M):
		if S[i]==T[j]:
			for k in range(i):
				for l in range(j):
					dp[i][j]+=dp[k][l]
			dp[i][j]+=1

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

print(ans)

Submission status: Runtime Error

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

for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]+1)%mod
        else:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]-dp[n][m]

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define int ll
const ll mod = 1000000007;

using namespace std;

int n, m;
int s[2010], t[2010];
int dp[2010][2010];

signed main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < m; i++) cin >> t[i];

    for (int i = 0; i <= 2009; i++) {
        for (int j = 0; j <= 2009; j++) {
            dp[i][j] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            dp[i][j] += mod - dp[i-1][j-1];
            if (s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] %= mod;
        }
    }

    cout << dp[n][m] << endl;
}

// 共通部分列

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = na()
t = na()
mod = 10**9+7

dp = [[0 for i in range(n + 2)] for j in range(m + 2)]

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][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[n][m]+1)%mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

n, m = LI()
ss = LI()
ts = LI()

dp = [[0 for _ in range(m)] for _ in range(n)]
dp2 = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n):
    for j in range(m):
        dp[i][j] = 1 if ss[i] == ts[j] else 0

index_d = defaultdict(list)

for i in range(n):
    for j in range(m):
        if i != 0:
            x = dp[n-i+1][n-j] 
        else:
            x = 0
        if j != 0:
            y = dp[n-i][n-j+1] 
        else:
            y = 0
        dp[n-i][n-j] = dp[n-i][n-j] + x + y
print((dp[0][0] + 1) % MOD)