시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

Have you ever seen a wave? It's a wonderful display of nature. Little Q is attracted to this wonderful thing, he even likes everything that looks like a wave. Formally, he says that a sequence $a_1, a_2, \ldots, a_n$ is a wavel if and only if $a_1 < a_2 > a_3 < a_4 > a_5 < a_6 \ldots$.

Now, given two sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$, Little Q wants to find two sequences $f_1, f_2, \ldots, f_k$ and $g_1, g_2, \ldots, g_k$ ($1 \leq f_i \leq n$, $f_i < f_{i + 1}$ and $1 \leq g_i \leq m$, $g_i < g_{i + 1}$) such that $a_{f_i} = b_{g_i}$ always holds and the sequence $a_{f_1}, a_{f_2}, \ldots, a_{f_k}$ is a wavel. Moreover, Little Q is wondering how many pairs of such sequences $f$ and $g$ exist. Please write a program to help him figure out the answer.

입력

The first line of the input contains two integers $n$ and $m$: the lengths of $a$ and $b$, respectively ($1 \leq n, m \leq 2000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$: the sequence $a$ ($1 \leq a_i \leq 2000$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$: the sequence $b$ ($1 \leq b_i \leq 2000$).

출력

Print a single line containing a single integer: the answer to the problem. As the answer can be very large, print it modulo $998\,244\,353$.

예제 입력 1

3 5
1 5 3
4 1 1 5 3

예제 출력 1

10

힌트

Here is the list of such sequences.

  1. $f=(1)$, $g=(2)$.
  2. $f=(1)$, $g=(3)$.
  3. $f=(2)$, $g=(4)$.
  4. $f=(3)$, $g=(5)$.
  5. $f=(1,2)$, $g=(2,4)$.
  6. $f=(1,2)$, $g=(3,4)$.
  7. $f=(1,3)$, $g=(2,5)$.
  8. $f=(1,3)$, $g=(3,5)$.
  9. $f=(1,2,3)$, $g=(2,4,5)$.
  10. $f=(1,2,3)$, $g=(3,4,5)$.