We start with a permutation $$$a_1, a_2, \ldots, a_n$$$ and with an empty array $$$b$$$. We apply the following operation $$$k$$$ times.
On the $$$i$$$-th iteration, we select an index $$$t_i$$$ ($$$1 \le t_i \le n-i+1$$$), remove $$$a_{t_i}$$$ from the array, and append one of the numbers $$$a_{t_i-1}$$$ or $$$a_{t_i+1}$$$ (if $$$t_i-1$$$ or $$$t_i+1$$$ are within the array bounds) to the right end of the array $$$b$$$. Then we move elements $$$a_{t_i+1}, \ldots, a_n$$$ to the left in order to fill in the empty space.
You are given the initial permutation $$$a_1, a_2, \ldots, a_n$$$ and the resulting array $$$b_1, b_2, \ldots, b_k$$$. All elements of an array $$$b$$$ are distinct. Calculate the number of possible sequences of indices $$$t_1, t_2, \ldots, t_k$$$ modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 100\,000$$$), denoting the number of test cases, followed by a description of the test cases.
The first line of each test case contains two integers $$$n, k$$$ ($$$1 \le k < n \le 200\,000$$$): sizes of arrays $$$a$$$ and $$$b$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$): elements of $$$a$$$. All elements of $$$a$$$ are distinct.
The third line of each test case contains $$$k$$$ integers $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$): elements of $$$b$$$. All elements of $$$b$$$ are distinct.
The sum of all $$$n$$$ among all test cases is guaranteed to not exceed $$$200\,000$$$.
For each test case print one integer: the number of possible sequences modulo $$$998\,244\,353$$$.
3 5 3 1 2 3 4 5 3 2 5 4 3 4 3 2 1 4 3 1 7 4 1 4 7 3 6 2 5 3 2 4 5
2 0 4
$$$\require{cancel}$$$
Let's denote as $$$a_1 a_2 \ldots \cancel{a_i} \underline{a_{i+1}} \ldots a_n \rightarrow a_1 a_2 \ldots a_{i-1} a_{i+1} \ldots a_{n-1}$$$ an operation over an element with index $$$i$$$: removal of element $$$a_i$$$ from array $$$a$$$ and appending element $$$a_{i+1}$$$ to array $$$b$$$.
In the first example test, the following two options can be used to produce the given array $$$b$$$:
In the second example test, it is impossible to achieve the given array no matter the operations used. That's because, on the first application, we removed the element next to $$$4$$$, namely number $$$3$$$, which means that it couldn't be added to array $$$b$$$ on the second step.
In the third example test, there are four options to achieve the given array $$$b$$$:
Name |
---|