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 .

Solution (Python):

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


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


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


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


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


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:
                dp[i][j] %= mod
    print(dp[n][m]%mod)
    return


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


if __name__ == "__main__":
    E()

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


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)

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

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

Solution (Python):



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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
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()

def main():
    N, M = LI()
    S = LI()
    T = LI()
    dp = [[1] * (M + 1)] + [[1] + [0] * M for _ in range(N)]
    for j in range(1, 1 + N):
        for i in range(1, 1 + M):
            if S[j - 1] == T[i - 1]:
                dp[j][i] = (dp[j][i - 1] + dp[j - 1][i]) % MOD
            else:
                dp[j][i] = (dp[j][i - 1] + dp[j - 1][i] - dp[j - 1][i - 1]) % MOD
    ans = dp[-1][-1]
    return ans

print(main())

Solution (Python):

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


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


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


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


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)
    
    for i in range(1,n+1):
        ai = bisect_left(dp, k + dp[i-1])
        ans += n+1 - ai
        
    print(ans)

    return


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


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    E()

Solution (Python):

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


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


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


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


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


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


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


if __name__ == "__main__":
    E()

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

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

Solution (Python):

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


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


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


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


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)
    
    for i in range(1,n+1):
        ai = bisect_left(dp, k + dp[i-1])
        ans += n+1 - ai
        
    print(ans)

    return


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


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    E()

Solution (Python):
MOD = 10**9+7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
dp[0][0] = 1
cum = [[0 for _ in range(m+1)] for _ in range(n+1)]
cum[0][0] = 1
for i in range(1, n+1):
	cum[i][0] = 1
for j in range(1, m+1):
	cum[0][j] = 1

for i in range(1, n+1):
	for j in range(1, m+1):
		if s[i-1] == t[j-1]:
			dp[i][j] = cum[i-1][j-1]
			dp[i][j] %= MOD
		cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + dp[i][j]
		cum[i][j] %= MOD

print(cum[n][m])

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

modulo = 10 ** 9 + 7


tab = [[s == t for s in S] for t in T]


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


for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        v  = tab[j + 1][i] + tab[j][i + 1]
        v -= 0 if tab[j][i] else tab[j + 1][i + 1]
        tab[j][i] = v % modulo

print(tab[0][0])

Solution (Python):
mod = 10**9+7
from bisect import bisect
from collections import defaultdict
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)]

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

print(dp[N-1][M-1]+1)

Solution (Python):
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(m + 1)] for j in range(n + 1)]

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

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

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

    DP = [[0 for j in range(M+1)] for i in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for i in range(1, N + 1): DP[i][0] = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1]) % mod
            else: 
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1] - DP[i][j]) % mod
    print(DP[N][M])
    return

if __name__ == "__main__":
    solve()

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

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

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

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, m = li()
s = list(li())
t = list(li())

MOD = 10**9 + 7

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

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

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

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

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

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

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

Solution (Python):
N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
MOD=10**9+7
dp=[]
for i in range(len(s)+1):
  dp.append([0]*(len(t)+1))
for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]: 
      dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]+1)%MOD
    else:
      dp[i+1][j+1] = dp[i+1][j]+dp[i][j+1]-dp[i][j]
print((dp[len(s)][len(t)]+1)%MOD)

Solution (Python):
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
acc = [0] * (M)
MOD = 10 ** 9 + 7
for s in S:
  ndp = [1]
  for i, t in enumerate(T):
    if s == t:
      ndp.append(ndp[-1] + dp[i+1])
      acc[i] = dp[i+1]
    else:
      ndp.append(ndp[-1] + acc[i])
  dp = ndp
print(dp[-1] % MOD)

Solution (Python):
MOD = 1000000007

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

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

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

Solution (Python):
import sys

readline = sys.stdin.readline

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

P = 10 ** 9 + 7

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

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

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

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

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

MOD = 10**9+7

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


dp[0][0] = 1 + int(S[0] == T[0])

for i in range(1,N):
  dp[i][0] = dp[i-1][0] + int(S[i]==T[0])
  
for j in range(1,M):
  dp[0][j] = dp[0][j-1] + int(T[j]==S[0])
  
for n in range(1,N):
  for m in range(1,M):
    dp[n][m] = (dp[n-1][m] + dp[n][m-1] - dp[n-1][m-1] + dp[n-1][m-1]*int(S[n]==T[m]))%MOD
    


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

Solution (Python):
mod = 10**9 + 7
def add(a,b):
    return (a+b)%mod

N,K = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
Slen = len(S);Tlen=len(T)
DP = [[0 for j in range(Tlen)] for i in range(Slen)]
DP[0][0] = 1 + (S[0] == T[0])
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if i==0 and j==0:continue
        if s == t:
            if i==0:
                DP[i][j]=DP[i][j-1]+1
            elif j==0:
                DP[i][j]=DP[i-1][j]+1
            else:
                DP[i][j]=(DP[i-1][j]+ DP[i][j-1])%mod
        else:
            if i==0:
                DP[i][j]=DP[i][j-1]
            if j==0:
                DP[i][j]=DP[i-1][j]
            else:
                DP[i][j]=(DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1])%mod
print(DP[Slen-1][Tlen-1]%mod)

Solution (Python):

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

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

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

        
        

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

    print(ans)






if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
MOD = 10**9 + 7
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
    for j in range(1, nt + 1):
        if (S[i - 1] == T[j - 1]):
            dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % MOD
        else:
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) %            MOD
print((dp[ns][nt] + 1) % MOD)

Solution (Python):

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

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

for i in range(1,n+1):
    for j in range(1,m+1):



        if s[i-1] == t[j-1]:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]) % MOD





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

Solution (Python):

"""
Created on Sun Jun 16 22:15:18 2019

@author: Yamazaki Kenichi
"""

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

A = [[1 for j in range(M+1)]]
A += [[0 for j in range(M+1)]]

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

    tmp2 = 0
    for j in range(M):

        if T[j] == S[i]:
            tmp = A[-1][j-1] % mod

        else:
            tmp = tmp2 % mod

        tmp2 = tmp
        A[-1][j] += tmp

        A[-1][j] %= mod

ans = A[-1][-2] % mod
print(ans)

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

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

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

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

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

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

bit = Bit(n + 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1) + 1)

print(bit.sum(n + 1) + 1)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]

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


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

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

mod = 10**9 + 7

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

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

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

print(dp[n][m])