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:
N, M = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

mod = 10 ** 9 + 7


def solve(x, y):
    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):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod
            if x[i - 1] == y[j - 1]:
                dp[i][j] += dp[i - 1][j - 1] + 1
                dp[i][j] %= mod
    return dp


ans = solve(s_list, t_list)
print((ans[N][M] + 1) % mod)

Submission status: Accepted

Solution code:
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()]
a=[1]*(m+1)
for b in s:
  d=a[:]
  k=0
  for j,c in enumerate(t):
    d[j]=(k+d[j])%1000000007
    if b==c:
      k=(k+a[j])%1000000007
  d[-1]=(k+d[-1])%1000000007
  a=d[:]
print(a[-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=[[0]*(M+1) for i in range(N+1)]
dp[0][0]=1
for i in range(N):
    dp[i+1][0]=1
for j in range(M):
    dp[0][j+1]=1
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1]+=dp[i][j]
        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:
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+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):
        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: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)
 
if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

print(dp[n][m] + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

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

Submission status: Accepted

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

def count_cs(str1, str2, MOD):
    '''
    計算量O(len(str1)*len(str2))
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + 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[len(str1)][len(str2)] + 1) % MOD

print(count_cs(s, t, MOD))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, S, T):

    MOD = 10**9 + 7
    dp0 = [1] * (M+1)
    for s in S:
        dp1 = dp0[:]
        k = 0
        for j, t in enumerate(T):
            if s == t:
                k += dp0[j]
            dp1[j+1] = (dp0[j+1] + k) % MOD
        dp0 = dp1

    return dp0[-1]


def main():
    N, M = read_int_n()
    S = read_int_n()
    T = read_int_n()
    print(slv(N, M, S, T))


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
W = [1] * (N + 1)
for i, t in enumerate(T):
	W2 = W[:]
	k = 0
	for j, s in enumerate(S):
		if t == s:
			k += W[j]
		W2[j + 1] = (W[j + 1] + k) % mod
	W = W2
print(W[-1])

Submission status: Accepted

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

dp0 = [[0 for _ in range(2005)] for _ in range(2005)]
dp1 = [[0 for _ in range(2005)] for _ in range(2005)]

dp0[0][0] = 1
for i in range(N + 1):
  for j in range(M + 1):
    dp0[i + 1][j] += dp0[i][j] % MOD
    dp1[i][j] += dp0[i][j] % MOD
    dp1[i][j + 1] += dp1[i][j] % MOD

    if S[i] == T[j]:
      dp0[i + 1][j + 1] += dp1[i][j] % MOD
ans = dp1[N][M]
print(ans % MOD)

Submission status: Accepted

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

modulo = 10 ** 9 + 7

# tab[j][i] = S[i] == T[j]
tab = [[s == t for s in S] for t in T]

# 番兵
for t in tab:
    t.append(1)
tab.append([1] * (len(S) + 1))

# 右下から計算
# tab[j][i] = S[i:]とT[j:]の等しい部分列の個数
for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        n  = tab[j+1][i] + tab[j][i+1] - tab[j+1][i+1]  # 包除原理
        n += tab[j+1][i+1] if tab[j][i] else 0  # S[i]とT[j]をマッチさせたとき
        tab[j][i] = n % modulo

print(tab[0][0])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    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 j in range(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-1][j]+dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mod
            if dp[i][j] >= mod:
                dp[i][j] %= mod
    print(dp[n][m])
    return

#F
def F():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

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

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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    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 j in range(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-1][j]+dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] < 0 or dp[i][j] >= mod:
                dp[i][j] %= mod
    print(dp[n][m])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = input().split()
        print(a,b,d)
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    ma = 100000000
    p = [0,ma/3,2*ma/3,ma]
    for i in range(100):
        x1 = [x[i]+f[i][0]*p[1] for i in range(n)]
        x2 = [x[i]+f[i][0]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        print(x1,p)
    a = sum(p)/4
    print(p)
    p = [-ma,2*ma/3-ma,2*ma/3*2-ma,ma]
    for i in range(100):
        x1 = [y[i]+f[i][1]*p[1] for i in range(n)]
        x2 = [y[i]+f[i][1]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
    b = sum(p)/4
    print(a,b)
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    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 j in range(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-1][j]+dp[i][j-1]
            else:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] >= mod or 0 > dp[i][j]:
                dp[i][j] %= mod
    print(dp[n][m])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = LS()
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    l = 0
    r = 100000000
    while r-l > 0.5:
        m = (l+r)/2
        px = [x[i]+f[i][0]*m for i in range(n)]
        py = [y[i]+f[i][1]*m for i in range(n)]
        dx = max(x)-min(x)
        dy = max(x)-min(y)
        if dx*dy < ans:
            ans = dx*dy

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

dp = []
for i in range(N+1):
	dp.append([0]*(M+1))
# print(dp)

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
ans = (dp[-1][-1] + 1) % 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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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


def f(N, M, S, T):
    W = [1]*(N+1)

    for i, t in enumerate(T):
        W2 = W[:]
        
        k = 0
        for j, s in enumerate(S):
            if t == s:
                k += W[j]

            x = (W2[j+1] + k)%1000000007
            W2[j+1] = x

        W = W2
        
    return W[-1]



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

    print(f(N,M,S,T))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a = LI()
    if x < a:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n, x = LI()
    L = LI()
    ans = 0
    c = 1
    for i in L:
        ans += i
        if ans <= x:
            c += 1
            continue
        break
    print(c)
    return

#C
def C():
    W, H, x, y = LI()
    a = W * H / 2
    b = 0
    if W/2 == x and H/2 == y:
        b = 1
    print(a,b)
    return

#D
def D():
    n, k = LI()
    a = LI()
    dp = [0] * (n)
    for i in range(n):
        dp[i] += dp[i - 1] + a[i]
    ans = 0
    dp.insert(0, 0)
    #print(dp)
    for i in range(1,n+1):
        ai = bisect_left(dp, k + dp[i-1])
        ans += n+1 - ai
        #print(ai, i, k + dp[i-1])
    print(ans)

    return

#E
def E():
    n, m = LI()
    s = LI()
    t = LI()
    dp = [[0] * (m+1) for i in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for k in range(m + 1):
        dp[0][k] = 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])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    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 j in range(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-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])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = input().split()
        print(a,b,d)
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    ma = 100000000
    p = [0,ma/3,2*ma/3,ma]
    for i in range(100):
        x1 = [x[i]+f[i][0]*p[1] for i in range(n)]
        x2 = [x[i]+f[i][0]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        print(x1,p)
    a = sum(p)/4
    print(p)
    p = [-ma,2*ma/3-ma,2*ma/3*2-ma,ma]
    for i in range(100):
        x1 = [y[i]+f[i][1]*p[1] for i in range(n)]
        x2 = [y[i]+f[i][1]*p[2] for i in range(n)]
        dx1 = max(x1)-min(x1)
        dx2 = max(x2)-min(x2)
        if dx1 < dx2:
            p[3] = p[2]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
        else:
            p[0] = p[1]
            p[1] = (p[3]-p[0])/3+p[0]
            p[2] = (p[3]-p[0])/3*2+p[0]
    b = sum(p)/4
    print(a,b)
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

ta = [[0] * (M+1) for i in range(N+1)]
ta[0][0]=1
wa = [[0] * (M+1) for i in range(N+1)]
wa[0][:]=[1]*(M+1)
for i in range(N+1):
    wa[i][0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i][j]=wa[i-1][j-1]
            wa[i][j]=(wa[i-1][j]+wa[i][j-1])%(10**9+7)
        else:
            wa[i][j]=(wa[i-1][j]+wa[i][j-1]-wa[i-1][j-1]+(10**9+7))%(10**9+7)
output = wa[N][M]
print(int(output))

Submission status: Accepted

Solution code:
mod=1000000007
n,m=map(int,input().split())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
DP=[[0]*(m+1) for _ 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][j+1]+DP[i+1][j]+1
        else:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]-DP[i][j]
        DP[i+1][j+1]%=mod
print((DP[-1][-1]+1)%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, a = LI()
    if x < a:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n, x = LI()
    L = LI()
    ans = 0
    c = 1
    for i in L:
        ans += i
        if ans <= x:
            c += 1
            continue
        break
    print(c)
    return

#C
def C():
    W, H, x, y = LI()
    a = W * H / 2
    b = 0
    if W/2 == x and H/2 == y:
        b = 1
    print(a,b)
    return

#D
def D():
    n, k = LI()
    a = LI()
    dp = [0] * (n)
    for i in range(n):
        dp[i] += dp[i - 1] + a[i]
    ans = 0
    dp.insert(0, 0)
    #print(dp)
    for i in range(1,n+1):
        ai = bisect_left(dp, k + dp[i-1])
        ans += n+1 - ai
        #print(ai, i, k + dp[i-1])
    print(ans)

    return

#E
def E():
    n, m = LI()
    s = LI()
    t = LI()
    dp = [[0] * (m+1) for i in range(n+1)]
    dp[0][0] = 0
    for i in range(n+1):
        dp[i][0] = 1
    for k in range(m + 1):
        dp[0][k] = 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])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()