Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  NL[i] = T.dfs(x, y, r)
ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  D = [[0] * N for _ in range(N)]
  cnt = 0
  f = 0
  for j in range(M):
    if t & 1:
      f += 1
      L = NL[j]
      n = L[0]
      for k in range(1, len(L)):
        m = L[k]
        x, y = min(n, m), max(n, m)
        if D[x][y] == 0:
          cnt += 1
        D[x][y] += 1
        n = m
    t >>= 1
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))

print(ans - c)

### FIXED CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
  a, b = ab[i][0] - 1, ab[i][1] - 1
  a, b = min(a, b), max(a, b)
  D[a][b] = i

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  L = T.dfs(x, y, r)
  n = L[0]
  t = 0
  for j in range(1, len(L)):
    m = L[j]
    x, y = min(n, m), max(n, m)
    t = t | (1 << D[x][y])
    n = m
  NL[i] = t
  

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  f = 0
  k = 0
  for j in range(M):
    if t & 1:
      f += 1
      k = k | NL[j]
    t >>= 1
  cnt = bin(k).count("1")
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))
print(ans - c)
### BUGGY CODE ###

import heapq as hp

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]

q = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            hp.heappush(q, (0, i, j))

while q:
    cnt, y, x = hp.heappop(q)
    for dy, dx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
        ny, nx = dy + y, dx + x
        if ny < 0 or nx < 0 or ny >= h or nx >= w:
            continue
        if not visited[ny][nx] and a[ny][nx] == '.':
            visited[ny][nx] = True
            hp.heappush(q, (cnt + 1, ny, nx))

print(cnt)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

q = deque([])
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append([i, j])
            q.append(0)

while q:
    y, x = q.popleft()
    ans = q.popleft() + 1
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        ny, nx = dy + y, dx + x
        if ny < 0 or nx < 0 or ny >= h or nx >= w:
            continue
        if a[ny][nx] == '.':
            a[ny][nx] = '#'
            q.append([ny, nx])
            q.append(ans)

print(ans-1)
### BUGGY CODE ###

n = int(input())
a = [int(input())for _ in range(n)]
o = a[::2]
e = a[1::2]
o.sort()
e.sort()
l = [0] * n
for i in range(n):
  if i % 2 == 0:
    l[i] = o[i // 2]
  else:
    l[i] = e[(i - 1) // 2]
ans = 0
for _ in range(n):
  for i in range(n - 1):
    if l[i] > l[i + 1]:
      ans += 1
      l[i], l[i + 1] = l[i + 1], l[i]
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
d = [{x: 0 for x in a} for _ in range(2)]
b = sorted(a)
for i in range(n):
    if i % 2:
        d[0][a[i]] += 1
        d[1][b[i]] += 1
t1 = 0
t2 = 0
for v1, v2 in zip(d[0].values(), d[1].values()):
    if v1 > v2:
        t1 += v1 - v2
print(t1)
### BUGGY CODE ###

n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
ans = 0

for j in range(1, n+1):
    flag = True
    for k in range(m):
        if l[k][0] <= j <= l[k][1]:
            continue
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())

L = 1
R = 10**5
ans = 1

for i in range(m):
    l, r = map(int, input().split())
    if L <= l <= R:
        L = l
    if L <= r <= R:
        R = r
    if R < l or r < L:
        ans = 0
        break

if ans != 0:
    ans = R - L + 1

print(ans)
### BUGGY CODE ###

s = input()
t = input()

j = 0
ans = 0

while j < len(t):
  ok=0
  for i in range(len(s)):
    ans += 1
    if t[j]==s[i]:
      ok=1
      j+=1
    if j >= len(t):
      break
  if not ok:
    print('-1')
    break
    
if ok:print(ans)

### FIXED CODE ###

import collections
import bisect
S = input()
T = input()
N = len(S)
 
d = collections.defaultdict(list)
for i, s in enumerate(S):
  d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
  if len(d[t])==0: # 存在しない文字ならFalse
    isOK = False
    break
  dic = d[t]
  idx = bisect.bisect_right(dic, i) # i番目以降におけるtの出現位置を取得(O(logN))
  if len(dic) == idx:
    i = dic[0]  # iをtのあるところに動かす
    end += 1    # 端に到達したら，繰り返し数を増やす
  else:
    i = dic[idx]# iをtのあるところに動かす

if isOK:
  ans = N * end + i
else:
  ans = -1
    
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n = int(input())
    wsv = LLI(n)
    wsv.sort(key=lambda x: x[0] + x[1], reverse=True)
    dp = {100000000: 0}
    # print(wsv)
    # print(dp)
    for w, s, v in wsv:
        for cap, value in sorted(dp.items()):
            nc = min(cap - w, s)
            if nc<0:continue
            if nc in dp:
                dp[nc] = max(dp[nc], value + v)
            else:
                dp[nc] = value + v
    # print(dp)
    print(max(dp.values()))

main()


### FIXED CODE ###

def f(n):
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
    print(max(dp))


n = int(input())
f(n)
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    b = []
    while a != []:
        for i in range(len(a)):
            if i == len(a) - 1 or a[i] * a[i + 1] < 0:
                b.append(sum(a[:i + 1]))
                a[:i + 1] = []
                break
    print(max(max(sum(b[j:j + i + 1]) for j in range(len(b) - i)) for i in range(len(b))))

### FIXED CODE ###

while True:
    n = int(input())
    if not n:
        break
    a = [int(input()) for _ in range(n)]
    for i in range(1, n):
        if a[i - 1] > 0:
            a[i] += a[i - 1]
    print(max(a))
### BUGGY CODE ###

N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

def base10to(n, b):
    if b <= n:
        return base10to(n//b, b) + str(n%b)
    return str(n%b)

num = 2**(len(base10to(N+1,2))+1)
seg = [0]*(2*num-1)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -float("inf")
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

num = 2
while num <= N+1:
    num *= 2

seg = [0]*(2*num-1)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -1
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))
### BUGGY CODE ###

n = int(input())

a = list(map(lambda x:int(x), input().split()))

junban = []

for i in range(n):
    jun = a.index(i+1)
    junban.append(str(jun+1))

print(" ".join(junban))


### FIXED CODE ###

n = int(input())

a = list(map(lambda x:int(x), input().split()))

junban = []
for i in range(n):
    junban.append(0)

for i in range(n):
    junban[a[i]-1] = str(i+1)



print(" ".join(junban))
### BUGGY CODE ###

N = int(input())

for i in range(1,N+1):
    ans = 0
    L = int(i**0.5)
    for x in range(1,L+1):
        for y in range(x,L+1):
            if (x*x+y*y+x*y)>i:
                break
            for z in range(y,L+1):
                num = x*x+y*y+z*z+x*y+y*z+z*x
                if num == i:
                    if x==y and y==z:
                        ans += 1
                    elif x==y or y==z or z==x:
                        ans += 3
                    else:
                        ans += 6
    print(ans)
        

### FIXED CODE ###

N = int(input())
A = [0]*(N+1)
L = int(N**0.5)+1
for x in range(1,L+1):
    for y in range(1,L+1):
        for z in range(1,L+1):
            num = x*x+y*y+z*z+x*y+y*z+z*x
            if num <= N:
                A[num] += 1
    

for i in range(1,N+1):
    print(A[i])
### BUGGY CODE ###

s = list(str(input()))
ans = 0
i = len(s) - 1 
while True:
    if i > len(s) - 1:
        i -= 2
    if i == 0:
        break
    if s[i] == "W" and s[i-1] == "B":
        s[i] = "B"
        s[i-1] = "W"
        ans += 1
        i += 1
    else:
        i -= 1
print(ans)

### FIXED CODE ###

s = list(str(input()))
count = 0
ans = 0
for i in s:
    if i == "B":
        count += 1
    else:
        ans += count
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
ans = set()
for i in range(10):
  for I in range(n-2):
    if s[I] == str(i):
      for j in range(10):
        for J in range(I+1,n-1):
          if s[J] == str(j):
            for l in range(10):
              for L in range(J+1,n):
                if s[L] == str(l):
                  ans.add(i*100+j*10+l)
print(len(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
def multi_index(l,x):
  return tuple([i for i,_x in enumerate(l) if _x == x])

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        for q in range(c+1,len(s)-1):
          if str(j) == s[q]:
            d = q
            break
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

SCORE=dict()

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE.get((i,j))!=None:
        return SCORE.get((i,j))+k
    if i==j:
        SCORE[(i,j)]=0
        return k

        

    if l==1:
        SCORE[(i,j)]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[(i,j)]+k
    if l==-1:
        SCORE[(i,j)]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[(i,j)]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i):
        for k in range(j,N+1):
            score(j,k,0,(-1)**(j+k+hand))

print(SCORE[(0,N)])


### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])
### BUGGY CODE ###

K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K,S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        z = S-(i+j)
        if 0 <= z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N=int(input())
L_list = list(map(int,input().split()))

def binary_search_left(list,target):
    '''
    配列に対してある数nを配列のソート順を崩さないように挿入するためのindexを返す関数。
    同一の数が配列に複数含まれていた場合は最も小さいindexを返す。
    '''
    result = -1
    left = 0
    right = len(list) - 1

    while left <= right:
        center = (left + right)//2
        if list[center] == target:          # 一致した場合
            if list[center - 1] == target:  # -> その一つ前も一致した場合、rightをcenterにしてもう一周
                right = center
            else:                           # -> その一つ前は一致しない場合、一番左で一致したということでcenterを返す
                return center
        elif list[center] < target:
            left = center + 1
        elif list[center] > target:
            right = center - 1
    return left                             # 一致したらcenterを返すが（上記）、なければleftのインデックスを返す

L_list = sorted(L_list)

ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = binary_search_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

print(ans)

### FIXED CODE ###

N=int(input())
L_list = list(map(int,input().split()))

import bisect

L_list = sorted(L_list)
 
ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = bisect.bisect_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

print(ans)
### BUGGY CODE ###

import sys, math, itertools, bisect, copy, re
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
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

bCnt = 0
for x in range(W):
    for y in range(H):
        if A[y][x] == '#':
            BQ.append((x, y))
            bCnt += 1


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0

while bCnt != H * W:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '#'
                newBQ.append((X, Y))
                bCnt += 1

    cnt += 1

    # print("len:{}".format(len(newBQ)))
    # for a in A:
    #     print(a)
    # print("---")

    BQ = newBQ

print(cnt)


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
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
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

bCnt = 0
for x in range(W):
    for y in range(H):
        if A[y][x] == '#':
            BQ.append((x, y))
            bCnt += 1


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0

while bCnt != H * W:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '#'
                newBQ.append((X, Y))
                bCnt += 1

    cnt += 1

    # print("len:{}".format(len(newBQ)))
    # for a in A:
    #     print(a)
    # print("---")

    BQ = newBQ

print(cnt)
### BUGGY 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)


### FIXED 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=[0]+LIST()
T=[0]+LIST()

dp = [[0] * (M+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        # dp配列を2次元累積和にして、動的に更新していく
        # (+-する添字位置は、普通の区間取得の時とは違う。どうなってるかは自分のメモ参照)
        dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD
        # 今回増やす数値が一致するなら
        if S[i] == T[j]:
            # そこより手前の全部合計+1
            dp[i][j]+=dp[i-1][j-1]+1
            dp[i][j]%=MOD
# 全部の合計+最初の空配列ペアの分
print((dp[N][M]+1)%MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
dic = {}
s = sum(a)
for i in range(1,10**5+1):
    if i in a:
        dic[i] = a.count(i)
    else:
        dic[i] = 0
lis=[]
for j in range(q):
    b,c = map(int,input().split())
    lis.append([b,c])

for p in lis:
    s += (p[1]-p[0])*dic[p[0]]
    dic[p[1]] += dic[p[0]]
    dic[p[0]] = 0
    print(s)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
num = Counter(a)
s = sum(a)
for _ in range(q):
    b,c = map(int,input().split())
    s += (c-b)*num[b]
    num[c] += num[b]
    num[b] = 0
    print(s)
### BUGGY CODE ###

import heapq
n,m = map(int, input().split())

a = list(map(int, input().split()))
heapq.heapify(a)

min_num = a[0]

tmp_array = []

for i in range(m):
  b,c = map(int, input().split())
  tmp_array.append([b,c])

sort_array = sorted(tmp_array, key=lambda x: x[0])

for i in range(m):
  b = sort_array[i][0]
  c = sort_array[i][1]
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

#for i in range(m):
#  b,c = map(int, input().split())
#  if min_num >= c:
#    continue
#  else:
#    for j in range(b):
#      if a[0] < c:
#        heapq.heappop(a)
#        heapq.heappush(a, c)
#      else:
#        break
#    min_num = a[0]

print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int, input().split())

a = list(map(int, input().split()))
heapq.heapify(a)

min_num = a[0]

tmp_array = []

for i in range(m):
  b,c = map(int, input().split())
  tmp_array.append([b,c])

sort_array = sorted(tmp_array, key=lambda x: -x[1])

for i in range(m):
  b = sort_array[i][0]
  c = sort_array[i][1]
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

#for i in range(m):
#  b,c = map(int, input().split())
#  if min_num >= c:
#    continue
#  else:
#    for j in range(b):
#      if a[0] < c:
#        heapq.heappop(a)
#        heapq.heappush(a, c)
#      else:
#        break
#    min_num = a[0]

print(sum(a))
### BUGGY CODE ###

in_ = [int(i) for i in input().split()]
L = in_[0]
R = in_[1]
mod_min = 100000
for i in range(L, R):
    for j in range(i+1, R+1):
        mod = i * j % 2019
        if mod < mod_min:
            mod_min = mod

print(mod_min)

### FIXED CODE ###

in_ = [int(i) for i in input().split()]
L = in_[0]
R = in_[1]
mod_min = 100000
# L = L % 2019
# R = R % 2019
# tab = [[-1 for r in range(R+1)] for l in range(L+1)]
# print(tab)
i_list = []
j_list = []
for i in range(L, R):
    i_mod = i % 2019
    for j in range(i+1, R+1):
            j_mod = j % 2019
            mod = i_mod * j_mod % 2019
            if mod < mod_min:
                mod_min = mod
                if mod_min == 0:
                    break
    if mod_min == 0:
        break
print(mod_min)