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: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp =[[0]*m for i in range(n)]
sum_ = [[0]*m for i in range(n)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i][j] = 1
            if i!=0 and j !=0:
                dp[i][j] = dp[i][j] +sum_[i-1][j-1]
                sum_[i][j] = dp[i][j] + sum_[i-1][j]+sum_[i][j-1]-sum_[i-1][j-1]
            elif i==0 and j == 0:
                dp[i][j] = 1
                sum_[i][j]= dp[i][j]
            elif i==0:
                dp[i][j] = 1
                sum_[i][j] = dp[i][j] + sum_[i][j-1]
            else:
                dp[i][j] = 1
                sum_[i][j] = dp[i][j] + sum_[i-1][j]
        else:
            dp[i][j] = 0
            if i!=0 and j !=0:
                sum_[i][j] = dp[i][j] + sum_[i-1][j]+sum_[i][j-1]-sum_[i-1][j-1]
            elif i==0 and j == 0:
                sum_[i][j]= dp[i][j]
            elif i==0:
                sum_[i][j] = dp[i][j] + sum_[i][j-1]
            else:
                sum_[i][j] = dp[i][j] + sum_[i-1][j]

print(sum_[n-1][m-1]+1)

Submission status: Wrong Answer

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(ret+1)#最後に空集合＋空集合を加える

Submission status: Wrong Answer

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+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]だけの組み合わせを足す
            ret += dp[i+1][j+1]
        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]
        
print(ret+1)#最後に空集合＋空集合を加える

Submission status: Wrong Answer

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+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]の総和

# 一旦空集合＋空集合は考えない
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]
        
print(dp_sum[N][M]+1)#最後に空集合＋空集合を加える

Submission status: Wrong Answer

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+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]の総和

# 一旦空集合＋空集合は考えない
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]だけの組み合わせを足す
        else:
            dp[i+1][j+1] = 0
        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]
        
print(dp_sum[N][M]+1)#最後に空集合＋空集合を加える

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
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 
ss=[0]*m
buf=[0]*m
count=0
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            if i==0 or j==0:
                dp[j]=1
                count+=1
                count=count%mod
            else:
                dp[j]=ss[j-1]+1
                count+=dp[j]
                count=count%mod
        if j>0:
            buf[j]=ss[j]+dp[j]+buf[j-1]-ss[j-1]
        else:
            buf[j]=ss[j]+dp[j]
    #ss=buf
    ss=deepcopy(buf)
print(count+1)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int, input().split())
MOD_n = 10**9 + 7
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

dp = np.zeros((N+1,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(dp[N][M] % MOD_n)

Submission status: Wrong Answer

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

dp = np.zeros((N+1,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(dp[N][M])

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

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

Submission status: Wrong Answer

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

mod = 10**9 + 7

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

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

def rec(i,j):
    if dp[i][j] != 0:
        return dp[i][j]
    if (i == 0 or j == 0):
        dp[i][j] = 1
        return 1
    if S[i-1] == T[j-1]:
        res = rec(i,j-1) + rec(i-1,j)
    else:
        res = rec(i,j-1) + rec(i-1,j) - rec(i-1,j-1)
    res %= mod
    dp[i][j] = res
    return res

ans = rec(N,M)
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


# BEGIN CUT HERE
MOD = 10**9 + 7
# MOD = 998244353  # AGC025_B


class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。
    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。
    '''

    def __init__(self, n, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n, self.mod)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return int(self.n)

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return pow(self.n, self.mod - 2, self.mod)

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __add__(self, other):
        self += other
        return self

    def __sub__(self, other):
        self -= other
        return self

    def __mul__(self, other):
        self *= other
        return self

    def __floordiv__(self, other):
        self //= other
        return self

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


class Combination():
    def __init__(self, sz):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [0] * (sz + 1)
        self._rfact = [0] * (sz + 1)
        self._fact[0] = 1
        self._rfact[sz] = 1
        for i in range(1, sz + 1):
            self._fact[i] = int(self._fact[i - 1] * Modint(i))
        self._rfact[sz] = Modint(self._fact[sz]).inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = int(self._rfact[i + 1] * Modint(i + 1))

    def fact(self, k: int) -> int:
        return self._fact[k]

    def rfact(self, k: int) -> int:
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）
        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[n - k])

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ
        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）
        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return 0
        return Modint(self._fact[n] * self._rfact[k] * self._rfact[n - k])

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。
        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）
        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return 0
        elif k == 0:
            return 1
        return self.C(n + k - 1, n)

# END CUT HERE


def ABC132_D():
    N, K = mi()
    res = Combination(N)
    for i in range(1, K + 1):
        print(res.C(K - 1, i - 1) * res.H(N - K - i + 1, i + 1))
# verified on 2019/07/01
# https://atcoder.jp/contests/abc132/tasks/abc132_d
# Python3: 32ms https://atcoder.jp/contests/abc132/submissions/6200580
# PyPy3だとオーバヘッドが大きいのか240msくらいかかるけど，基本はPyPyで良いと思う。


def AGC025_B():
    N, A, B, K = mi()
    res = Combination(N)
    ans = Modint(0)
    for a in range(min(K // A + 1, N + 1)):
        b = (K - a * A) // B
        if A * a + B * b == K and a >= 0 and b >= 0:
            ans += res.C(N, a) * res.C(N, b)
    print(ans)
# verified on 2019/07/01
# https://atcoder.jp/contests/agc025/tasks/agc025_b
# PyPy3: https://atcoder.jp/contests/agc025/submissions/6200598
# Python3だとTLE


def ABC130_E():
    N, M = mi()
    S = lmi()
    T = lmi()
    a = [[Modint(0) for __ in range(M + 1)] for _ 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] = Modint(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 Modint(0))
    print(a[N][M])


if __name__ == '__main__':
    # ABC132_D()
    # AGC025_B()
    ABC130_E()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
N,M = map(int,input().split())
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):
    for j in range(M+1):
        if S[i]==T[j-1]:
            dp[i+1][j]=(dp[i+1][j-1] + dp[i][j])%(10**9+7)
        else:
            dp[i+1][j]=(dp[i+1][j-1] +dp[i][j]-dp[i][j-1])%(10**9+7)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
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):
    for j in range(M+1):
        if S[i]==T[j-1]:
            dp[i+1][j]=dp[i+1][j-1] + dp[i][j]
        else:
            dp[i+1][j]=dp[i+1][j-1] +dp[i][j]-dp[i][j-1]
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(shape=(n, m))

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            if i == 0:
                dp[i, j] = sum(dp[:i, :j]) + 1
            else:
                dp[i, j] = sum(sum(dp[:i, :j])) + 1
        else:
            dp[i, j] = 0

print((sum(sum(dp)) + 1) % mod)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

tempArray = [1]*(M + 1)
for i, x in enumerate(S):
  tempArray2 = tempArray[:]
  k = 0
  for j, y in enumerate(T):
    if x == y:
      k += tempArray[j]
    tempArray2[j + 1] = tempArray[j + 1] + k
  tempArray = tempArray2
print(tempArray[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    #cnt = [[0] * (M) for _ in range(N)]

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            #cnt[i][j] = c
            d = rui[i+1][j] + rui[i][j+1] - rui[i][j] + c
            if d >= MOD:
                d -= MOD
            rui[i+1][j+1] = d
            n += c
            if n >= MOD:
                n -= MOD

    #for v in cnt:
    #    n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()

Submission status: Wrong Answer

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

total = [0]*(N+1)*(M+1)
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			n = total[(M+1)*i+j] + 1
		else:
			n = 0
		total[(M+1)*(i+1)+(j+1)] = n + total[(M+1)*i+(j+1)] + total[(M+1)*(i+1)+j] - total[(M+1)*i+j]
print(total[-1]+1)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [[0 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 a[i - 1] == b[j - 1]:
            dp[i][j] = 1 + dp[i - 1][j] + dp[i][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD

ret = dp[n][m] + 1
if ret >= MOD:
    ret -= MOD
print(ret)

Submission status: Wrong Answer

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

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

ans = dp[N][M]

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

dp_sum = [0] * (M + 1)

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

print((dp_sum[M] + 1) % MOD)

Submission status: Wrong Answer

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

x = 2160
dp = [[0]*x for i in range(x)]
sum2d = [[0]*x for i in range(x)]
sum2d[0][0] = 1
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = sum2d[i][j] + 1
        sum2d[i+1][j+1] = (dp[i+1][j+1]+sum2d[i][j+1]+sum2d[i+1][j]-sum2d[i][j])%mod
print((sum2d[N][M]+1)%mod)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
dp=[[0]*(1+M) for i in range(1+N)]
dp[0][0]=1
mod=10**9+7
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1]=1
ans=[[0]*(1+M) for i in range(1+N)]
ans[0][0]=1
x=0
ans[0]=[1 for i in range(1+M)]
for i in range(1,1+N):
    ans[i][0]=ans[i-1][0]
    for j in range(1,1+M):
        if S[i-1]==T[j-1]:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1])%mod
        else:
            (ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1])%mod
print(ans[N][M])

Submission status: Wrong Answer

Solution code:
# Python3 program to count common 
# subsequence in two strings 

# return the number of common subsequence 
# in two strings 
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 each character of S 
	for i in range(1, n1 + 1): 

		# for each charcater in T 
		for j in range(1, n2 + 1): 

			# if character are same in both 
			# the string 
			if (s[i - 1] == t[j - 1]): 
				dp[i][j] = (1 + 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])		 
		
	return dp[n1][n2] 

# Driver Code 
N,M = map(int,input().split())
s = "".join(list(map(str,input().split())))
t = "".join(list(map(str,input().split())))

print(CommomSubsequencesCount(s, t) + 1) 

# This code is contributed by Mohit Kumar

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m+2) for _ in range(n+2)]
mod = 1000000007

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0] * (m+2) for _ in range(n+2)]
mod = 1000000007
dp[0][0] = 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] += 1 + dp[i-1][j-1]
            dp[i][j] %= mod
print(dp[n][m])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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 each character of S
    for i in range(1, n1 + 1):

        # for each charcater in T
        for j in range(1, n2 + 1):

            # if character are same in both
            # the string
            if (s[i - 1] == t[j - 1]):
                dp[i][j] = (1 + 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])

    return dp[n1][n2]


def solve():
    _, _ = [int(i) for i in input().split()]
    s = [int(i) for i in input().split()]
    t = [int(i) for i in input().split()]
    print(commomSubsequencesCount(s, t) + 1)

solve()

Submission status: Wrong Answer

Solution code:
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 each character of S
    for i in range(1, n1 + 1):

        # for each charcater in T
        for j in range(1, n2 + 1):

            # if character are same in both
            # the string
            if (s[i - 1] == t[j - 1]):
                dp[i][j] = (1 + 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])

    return dp[n1][n2]


def solve():
    _, _ = [int(i) for i in input().split()]
    s = input().replace(" ", "")
    t = input().replace(" ", "")
    print(commomSubsequencesCount(s, t) + 1)

solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    if N <=M :
        *T, = map(int, input().split())
        S = map(int, input().split())
        dp = [0]*(N+1)
    else:
        S = map(int, input().split())
        *T, = map(int, input().split())
        dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s is t else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    *T, = map(int, input().split())
    *S, = map(int, input().split())
    dp = [0]*(N+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s is t else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    *T, = map(int, input().split())
    *S, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s is t else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())