CodeEff/ECCO huggingface dataset:
# Original solution
def c_takahashi_information(C):
    a = []
    b = []
    for a_0 in range(min(C[0]) + 1):
        for a_1 in range(min(C[1]) + 1):
            for a_2 in range(min(C[2]) + 1):
                tmp1 = [a_0, a_1, a_2]
                tmp2 = [[C[i][j] - tmp1[i]
                         for j in range(3)] for i in range(3)]
                tmp2 = list(map(list,set(map(tuple, tmp2))))
                a.append(tmp1)
                b.append(tmp2)
    for aa, bb in zip(a, b):
        for bbb in bb:
            f = True
            for i in range(3):
                for j in range(3):
                    if aa[i] + bbb[j] != C[i][j]:
                        f = False
                        break
                if not f:
                    break
            if f:
                return 'Yes'
    return 'No'
  
C = [[int(i) for i in input().split()] for j in range(3)]
print((c_takahashi_information(C)))

# Optimized solution
def c_takahashi_information(C):
    a = [min(C[0]), min(C[1]), min(C[2])]
    tmp = [[C[i][j] - a[i] for j in range(3)] for i in range(3)]
    b = list(map(list, set(map(tuple, tmp))))
    for bb in b:
        f = True
        for i in range(3):
            for j in range(3):
                if a[i] + bb[j] != C[i][j]:
                    f = False
                    break
            if not f:
                break
        if f:

            return 'Yes'
    return 'No'
  
C = [[int(i) for i in input().split()] for j in range(3)]
print((c_takahashi_information(C)))
# Original solution
def c_takahashi_information(C):
    a = [min(C[0]), min(C[1]), min(C[2])]
    tmp = [[C[i][j] - a[i] for j in range(3)] for i in range(3)]
    b = list(map(list, set(map(tuple, tmp))))
    for bb in b:
        f = True
        for i in range(3):
            for j in range(3):
                if a[i] + bb[j] != C[i][j]:
                    f = False
                    break
            if not f:
                break
        if f:

            return 'Yes'
    return 'No'
  
C = [[int(i) for i in input().split()] for j in range(3)]
print((c_takahashi_information(C)))

# Optimized solution
def c_takahashi_information(C):
    b = [C[0][i] - 0 for i in range(3)]
    a = [0] + [C[i][0] - b[0] for i in range(1, 3)]  # a_1=0と仮定してよい
    for i in range(3):
        for j in range(3):
            if a[i] + b[j] != C[i][j]:
                return 'No'
    return 'Yes'

C = [[int(i) for i in input().split()] for j in range(3)]
print((c_takahashi_information(C)))
# Original solution
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

A = list([x-min(a) for x in a])
B = list([x-min(b) for x in b])
C = list([x-min(c) for x in c])

A.sort()
B.sort()
C.sort()

if A==B==C:
    print('Yes')
else:
    print('No')

# Optimized solution
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

A = list([x-min(a) for x in a])
B = list([x-min(b) for x in b])
C = list([x-min(c) for x in c])

if A==B==C:
    print('Yes')
else:
    print('No')
# Original solution
def main():
    c11, c12, c13 = list(map(int, input().split()))
    c21, c22, c23 = list(map(int, input().split()))
    c31, c32, c33 = list(map(int, input().split()))

    r1max = max([c11, c12, c13])
    r2max = max([c21, c22, c23])
    r3max = max([c31, c32, c33])
    c1max = max([c11, c21, c31])
    c2max = max([c12, c22, c32])
    c3max = max([c13, c23, c33])
    for a1 in range(0, r1max + 1):
        for a2 in range(0, r2max + 1):
            for a3 in range(0, r3max + 1):
                for b1 in range(0, c1max + 1):
                    C11 = a1 + b1
                    C21 = a2 + b1
                    C31 = a3 + b1
                    if C11 == c11 and C21 == c21 and C31 == c31:
                        for b2 in range(0, c2max + 1):
                            C12 = a1 + b2
                            C22 = a2 + b2
                            C32 = a3 + b2
                            if C12 == c12 and C22 == c22 and C32 == c32:
                                for b3 in range(0, c3max + 1):
                                    C13 = a1 + b3
                                    C23 = a2 + b3
                                    C33 = a3 + b3
                                    if C13 == c13 and C23 == c23 and C33 == c33:
                                        print('Yes')
                                        return

    print('No')
    return


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    c11, c12, c13 = list(map(int, input().split()))
    c21, c22, c23 = list(map(int, input().split()))
    c31, c32, c33 = list(map(int, input().split()))

    r1max = max([c11, c12, c13])
    r2max = max([c21, c22, c23])
    r3max = max([c31, c32, c33])
    c1max = max([c11, c21, c31])
    c2max = max([c12, c22, c32])
    c3max = max([c13, c23, c33])
    for a1 in range(0, r1max + 1):
        for a2 in range(0, r2max + 1):
            for a3 in range(0, r3max + 1):
                m = max([a1, a2, a3])
                for b1 in range(0, c1max - m + 1):
                    C11 = a1 + b1
                    C21 = a2 + b1
                    C31 = a3 + b1
                    if C11 == c11 and C21 == c21 and C31 == c31:
                        for b2 in range(0, c2max - m + 1):
                            C12 = a1 + b2
                            C22 = a2 + b2
                            C32 = a3 + b2
                            if C12 == c12 and C22 == c22 and C32 == c32:
                                for b3 in range(0, c3max - m + 1):
                                    C13 = a1 + b3
                                    C23 = a2 + b3
                                    C33 = a3 + b3
                                    if C13 == c13 and C23 == c23 and C33 == c33:
                                        print('Yes')
                                        return

    print('No')
    return


if __name__ == '__main__':
    main()
# Original solution
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
import sys
N, K = [int(x) for x in sys.stdin.readline().split(' ')]
lines = sys.stdin.readlines()


schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [0]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if(schedule[0]!=l2+1 and schedule[0]!=0):
        number[i] = 0
    elif(schedule[1]!=l1+1 and schedule[1]!=0):
        number[i] = 0
    else:
        number[i] = 1


for s in schedule[2:]:
    new_number = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
        for j in range(3):
            new_number[i] += number[l2*3 + j] if((s==0 or s==l1+1) and  not (l2==j and l1==j)) else 0
    for i in range(9):
        number[i] = new_number[i] % 10000
sum = 0
for n in number:
    sum += n
print((sum % 10000))

# Optimized solution
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
from sys import stdin
N, K = [int(x) for x in stdin.readline().split(' ')]
lines = stdin.readlines()

schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [1]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if   schedule[0]!=l2+1 and schedule[0]!=0:
        number[i] = 0
    elif schedule[1]!=l1+1 and schedule[1]!=0:
        number[i] = 0

for s in schedule[2:]:
    tmp = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
       	tmp[i] = [number[l2*3+j] for j in range(3) \
         if (s==0 or s==l1+1) and  not (l2==j and l1==j)]
    for i in range(9):
         number[i] = sum(tmp[i])
print((sum(number) % 10000))
# Original solution
#coding:utf-8
 
import sys
import copy
 
def main():
    line = sys.stdin.readline()
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return
 
def analy(line):
    field = [int(n) for n in line.split()]
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        data.append(b)
    print((compute(field, data)))
 
def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
                if i == 0 :
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]
 
if __name__ == "__main__":
    main()

# Optimized solution
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #整列
    field = [int(n) for n in line.split()]
    # 横、縦
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #横、縦
        data.append(b)
    print((compute(field, data)))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #横→縦に移動していく
                if i == 0 :
                    #一番下
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #左がない
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()
# Original solution
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.append(0)
T.append(0)
MAX = 2005
dp0 = [[0] * MAX for _ in range(MAX)]
dp1 = [[0] * MAX for _ in range(MAX)]

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
print((dp1[N][M] % MOD))


# Optimized solution
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M = list(map(int, input().split()))
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
 
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp_cum[0][0] = 1
for n in range(N+1):
    dp_cum[n][0] = 1
for m in range(M+1):
    dp_cum[0][m] = 1
  
for n in range(1,N+1):
    for m in range(1,M+1):
        now = 0
        if S[n] == T[m]:
            now = dp_cum[n-1][m-1]
        dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + now
        dp_cum[n][m] %= MOD
print((dp_cum[N][M]))
# Original solution
MOD = 10 ** 9 + 7

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

sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
    sdp[i + 1][j + 1] = v % MOD

print((sdp[-1][-1] + 1))
# for row in sdp:
#  print(('{: 4d} ' * len(row)).format(*row))
## print(sdp)

# Optimized solution
MOD = 10 ** 9 + 7


def main(S, T):
  sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  for i, s in enumerate(S):
    for j, t in enumerate(T):
      v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
      sdp[i + 1][j + 1] = v % MOD

  return (sdp[-1][-1] + 1)


if __name__ == '__main__':
  _, _ = list(map(int, input().strip().split()))
  S = input().strip().split()
  T = input().strip().split()
  # S = range(1000)
  # T = range(1000)
  print((main(S, T)))
# Original solution
MOD = 10 ** 9 + 7


def main(S, T):
  sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  for i, s in enumerate(S):
    for j, t in enumerate(T):
      v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
      sdp[i + 1][j + 1] = v % MOD

  return (sdp[-1][-1] + 1)


if __name__ == '__main__':
  _, _ = list(map(int, input().strip().split()))
  S = input().strip().split()
  T = input().strip().split()
  # S = range(1000)
  # T = range(1000)
  print((main(S, T)))

# Optimized solution
MOD = 10 ** 9 + 7


def main(S, T):
  l = len(T) + 1
  dp = [0] * l
  # sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  # for i, s in enumerate(S):
  #  for j, t in enumerate(T):
  #    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
  #    sdp[i + 1][j + 1] = v % MOD
  for i, s in enumerate(S):
    tmp = [0] * l
    for j, t in enumerate(T):
      v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
      tmp[j + 1] = v % MOD
    dp = tmp

  # return (sdp[-1][-1] + 1)
  return dp[-1] + 1


if __name__ == '__main__':
  if True:
    _, _ = list(map(int, input().strip().split()))
    S = input().strip().split()
    T = input().strip().split()
  else:
    S = list(range(1000))
    T = list(range(1000))
  print((main(S, T)))
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 16 20:56:46 2019

@author: Yamazaki Kenichi
"""

N, M = list(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)] for i in range(N)]
A += [[1 for j in range(M+1)]]
for i in range(N):
#    print(i,j)
    for j in range(M):
#        print(i,j)
        if T[j] == S[i]:
            A[i+1][j] = A[-1][j-1] % mod
        else:
            A[i+1][j] = A[i+1][j-1] % mod
        A[-1][j] += A[i+1][j]
        A[-1][j] %= mod
#        print(A)
ans = A[-1][-2]
print(ans)

# Optimized solution
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 16 22:15:18 2019

@author: Yamazaki Kenichi
"""

N, M = list(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 += [[0 for j in range(M+1)] for i in range(N)]
A += [[1 for j in range(M+1)]]
for i in range(N):
#    print(i,j)
    tmp2 = 0
    for j in range(M):
#        print(i,j)
        if T[j] == S[i]:
            tmp = A[-1][j-1] % mod
#            A[i+1][j] = A[-1][j-1] % mod
        else:
            tmp = tmp2 % mod
#            A[i+1][j] = A[i+1][j-1] % mod
        tmp2 = tmp
        A[-1][j] += tmp
#        A[-1][j] += A[i+1][j]
        A[-1][j] %= mod
#        print(A)
ans = A[-1][-2] % mod
print(ans)
# Original solution
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(eval(input()))
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      list(map(int, input().split()))
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

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

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
        if j==14:
            ddprint("dp {} z {} acc {}".format(dp[z-1][j-1], z, acc[z]))
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R
        if i==18 and j==14:
            ddprint("{}  {}  {}".format(dp[i][j-1], acc[i], t[j]==s[0]))
        ddprint("i {} j {} dpij {}".format(i,j,dp[i][j]))

if DBG:
    for i in range(n):
        print((dp[i]))
print(((dp[n-1][m-1]+1)%R))


# Optimized solution
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(eval(input()))
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      list(map(int, input().split()))
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

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

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R

if DBG:
    for i in range(n):
        print((dp[i]))
print(((dp[n-1][m-1]+1)%R))
# Original solution
#解説読み 2次元dp
mod = 10**9 + 7
n,m = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
tmp = [1 for _ in range(m+1)]
dp = [tmp]
for ni in range(n):
  last = tmp
  tmp = [1]
  for mi in range(m):
    if A[ni] != B[mi]:
      x = tmp[-1]+last[mi+1]-last[mi]
    else:
      x = tmp[-1]+last[mi+1]
    x %= mod
    tmp.append(x)
  dp.append(tmp)
print((dp[-1][-1]))

# Optimized solution
#15:35
h,w = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))
mod = 10 ** 9 + 7
now = [1 for _ in range(w+1)]
for i in range(h):
  last = now
  now = [1]
  for j in range(w):
    if a[i] == b[j]:
      now.append((last[j+1]+now[-1])%mod)
    else:
      now.append((last[j+1]+now[-1]-last[j])%mod)
  #print(now)
print((now[-1]))
# Original solution
from collections import defaultdict
import sys
from copy import copy
input = sys.stdin.readline
mod = 10**9+7
N, M = list(map(int, input().split()))
S = "".join(input().split())
T = "".join(input().split())
dS = defaultdict(int)
dT = defaultdict(int)
dS[""] += 1
dT[""] += 1
for i in range(N):
    tmp = copy(dS)
    for key in tmp:
        dS[key+S[i]] += tmp[key]

for i in range(M):
    tmp = copy(dT)
    for key in tmp:
        dT[key+T[i]] += tmp[key]
    
ans = 0
for key in dS:
    ans += dS[key]*dT[key]%mod

print((ans%mod))


# Optimized solution
mod = 10**9 + 7
N, M = list(map(int, input().split()))
S = [None] + list(map(int, input().split()))
T = [None] + list(map(int, input().split()))
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] + 1)%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))
# Original solution
n,m=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
sum[0][0]=dp[0][0]
for i in range(1,n):
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(1,m):
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
ans=0
for i in range(n):
  for j in range(m):
    ans+=dp[i][j]
    ans=ans%mod
print(((ans+1)%mod))

# Optimized solution
n,m=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
ans=0
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
  ans+=dp[i][0]  
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
  ans+=dp[0][i]
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
    ans+=dp[i][j]
    ans%=mod
print(((ans-dp[0][0]+1)%mod))
# Original solution
n,m=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
ans=0
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
  ans+=dp[i][0]  
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
  ans+=dp[0][i]
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
    ans+=dp[i][j]
    ans%=mod
print(((ans-dp[0][0]+1)%mod))

# Optimized solution
n,m=list(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)]
sum=[[0]*(m+1) for _ in range(n+1)]
mod=10**9+7
ans=0
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=(sum[i][j]+1)%mod
    else:
      dp[i+1][j+1]=0
    sum[i+1][j+1]=(sum[i][j+1]+sum[i+1][j]-sum[i][j]+dp[i+1][j+1])%mod
    ans+=dp[i+1][j+1]
    ans%=mod
print(((ans+1)%mod))