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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    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: Time Limit Exceeded

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

    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]
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
    print(DP[n][m] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

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]
        if S[n - 1] == T[m - 1]:
            DP[n][m] += DP[n - 1][m - 1]

print(DP[n][m] % MOD)

Submission status: Time Limit Exceeded

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


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

DP = [[0] * (M + 1) for _ in range(N + 1)]
DP[0][0] = 1
for n in range(N + 1):
    for m in range(M + 1):
        if n > 0 and m > 0 and S[n - 1] == T[m - 1]:
            for nn in range(n):
                for mm in range(m):
                    DP[n][m] += DP[nn][mm]

print(sum(sum(DP, [])) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        if S[i] != T[j]:
            total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        else:
            total[I][J] = (total[I][J-1] + total[I-1][J] + 1) % MOD
        
print((total[N][M] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
dp = [[0 for j in range(M+2)] for i in range(N+2)]
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        if S[i] != T[j]:
            continue
        
        dp[I][J] = total[I-1][J-1] + 1
        total[I][J] = (total[I][J] +  dp[I][J]) % MOD
print(dp[N+1][M+1])

Submission status: Time Limit Exceeded

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

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+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
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

# S -> T
relation_list = []
for s in S:
    buffer = []
    for j, t in enumerate(T):
        if t == s:
            buffer.append(j)
    relation_list.append(buffer)

pattern = defaultdict(int)

for relation in relation_list[::-1]:
    for j in relation:
        pattern[j] += sum([value for key, value in pattern.items() if key > j]) + 1

print((sum(pattern.values()) + 1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:

n,m=map(int,input().split())
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
maxim=(10**3)*2
mod=10**9+7
dp=[[0 for i in range(m+1)]for j in range(n+1)]

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

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
S=LIST()
T=LIST()

# dp1[i][j], dp2[i][j] := Sをi文字目、Tをj文字目まで考えた時、dp1はi方向、dp2はj方向に遷移させる
dp1=list2d(N+2, M+2, 0)
dp2=list2d(N+2, M+2, 0)
dp1[0][0]=1
for i in range(N+1):
    for j in range(M+1):
        dp1[i][j]%=MOD
        # 数え上げをi方向とj方向で重複がないように遷移させる
        dp1[i+1][j]+=dp1[i][j]
        dp2[i][j]+=dp1[i][j]
        dp2[i][j+1]+=dp2[i][j]
        # 今回増やす数値が一致するなら
        if i<N and j<M and S[i]==T[j]:
            # 斜めに遷移させる(1→0)
            dp1[i+1][j+1]+=dp2[i][j]
print((dp2[N][M])%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import bisect
from collections import Counter
from collections import defaultdict
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


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]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        dp[i+1][j+1] = (S[i] == T[j]) * sum[i][j]
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        dp[i+1][j+1] = (S[i] == T[j]) * sum[i][j] % MOD
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])

Submission status: Time Limit Exceeded

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
            rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + c
            n = (n + c) % MOD

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

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

main()

Submission status: Time Limit Exceeded

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

    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
            rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + c

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint
 
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 + 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):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
    #pprint(dp)
    ret = dp[N][M] % MOD
    print(ret)
    return
 
 
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]"
    solve(N, M, S, T)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

MOD = int(1e9 + 7)

def f(N, M, s, t):
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        cumsi = cums[i]
        cumsi1 = cums[i+1]
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = cumsi[j] + 1
            cumsi1[j+1] = \
                (cumsi1[j] + cumsi[j+1] + MOD - cumsi[j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

MOD = int(1e9 + 7)

def f(N, M, s, t):
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = (cums[i][j] + 1) % MOD
            cums[i+1][j+1] = \
                (cums[i+1][j] + cums[i][j+1] + MOD - cums[i][j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * M for _ in range(N)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = (cums[i][j] + 1) % MOD
            cums[i+1][j+1] = \
                (cums[i+1][j] + cums[i][j+1] + MOD - cums[i][j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Time Limit Exceeded

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

for r in range(1, N+1):
    for k in range(1, M+1):
        if S[r-1] == T[k-1]:
            dp[r][k] = 1+dp[r-1][k]+dp[r][k-1]
            dp[r][k] %= MOD
        else:
            dp[r][k] = dp[r-1][k]+dp[r][k-1]-dp[r-1][k-1]
            dp[r][k] %= MOD
print((dp[-1][-1]+1) % MOD)

Submission status: Time Limit Exceeded

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

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = [-1] + S
T = [-1] + T

# dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# S[i] != T[j] のとき 0
# S[i] == T[j] のとき、sum(dp[:i][:j])
dp = np.zeros((len(S), len(T)), dtype=int)
dp[0][0] = 1
# dp の二次元累積和
cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    for j in range(1, len(T)):
        if S[i] != T[j]:
            continue
        # dp[i][j] = dp[:i, :j].sum() % MOD
        dp[i][j] = cumsum[j - 1] % MOD
    cumsum += dp[i].cumsum()
    cumsum %= MOD
print(cumsum[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = [[1] * (m + 1)]
for i in range(n):
  f.append([1] + [0] * m)
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: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

dp, dp_sum = [0] * M, [0] * (M + 1)

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

dp, dp_sum = [0] * M, [0] * (M + 1)

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

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

Submission status: Time Limit Exceeded

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(M, dtype=int)
dp_sum = np.zeros(M + 1, dtype=int)

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

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

Submission status: Time Limit Exceeded

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(M, dtype=int)
dp_sum = np.zeros(M + 1, dtype=int)

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

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

Submission status: Time Limit Exceeded

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_sum[N][M] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
N, M = map(int, input().split())

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

memo = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
_sum = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
memo[0][0] = 1


for i in range(1, N + 1):
  _i = i - 1
  for j in range(1, M + 1):
    _j = j - 1
    if S[_i] == T[_j]:
      memo[i][j] = _sum[_i][_j] + 1
    _sum[i][j] = _sum[_i][j] + _sum[i][_j] - _sum[_i][_j] + memo[i][j]


print(_sum[-1][-1] % int(10**9 + 7) + 1)

Submission status: Time Limit Exceeded

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((np.sum(dp) + 1) % MOD)

Submission status: Time Limit Exceeded

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 i in range(n+1)]
for i in range(m+1):
	dp[0][i]=1
for j in range(n+1):
	dp[j][0]=1
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%1000000007
		else:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j]-dp[i][j])%1000000007
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

INF = 10**9+7
def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    N, M = rli()
    ls = rli()
    lt = rli()

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

    for n in range(N):
        s = ls[n]
        for m in range(M):
            t = lt[m]
            if s == t:
                dp[n][m] = 1
                if n > 0 and m > 0:
                    dp[n][m] += sdp[n-1][m-1]
            else:
                dp[n][m] = 0
            sdp[n][m] = dp[n][m]
            if n > 0:
                sdp[n][m] += sdp[n-1][m]
            if m > 0:
                sdp[n][m] += sdp[n][m-1]
            if n > 0 and m > 0:
                sdp[n][m] -= sdp[n-1][m-1]
            if sdp[n][m] > INF:
                sdp[n][m] %= INF
    print(sdp[N-1][M-1]+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)]
mod=10**9+7
def Mod(n,mod):
    return n-mod if n>=mod else n
for n in range(1,N+1):
    for m in range(1,M+1):
        x=dp[n-1][m-1]+1 if S[n-1]==T[m-1] else 0
        dp[n][m]=Mod(dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]+x,mod)
print((dp[-1][-1]+1)%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

N, M = list(map(int, input().rstrip().split(' ')))
S = list(map(int, input().rstrip().split(' ')))
T = list(map(int, input().rstrip().split(' ')))
dp = [[0] * (N + 1) for _ in range(M + 1)]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

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 + 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):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
    #pprint(dp)
    ret = dp[N][M] % MOD
    print(ret)
    return


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]"
    solve(N, M, S, T)

if __name__ == '__main__':
    main()