19041번 - Wavel Sequence 다국어

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$.

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)$.