Identify the Operations
Contest: VK Cup 2019-2020 - Final Round (Engine)
Difficulty rating: 1800
Tags: combinatorics, greedy

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

Input format:
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$$$.

Output format:
For each test case print one integer: the number of possible sequences modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
$$$\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$$$:

- $$$1 2 \underline{3} \cancel{4} 5 \rightarrow 1 \underline{2} \cancel{3} 5 \rightarrow 1 \cancel{2} \underline{5} \rightarrow 1 2$$$; $$$(t_1, t_2, t_3) = (4, 3, 2)$$$;
- $$$1 2 \underline{3} \cancel{4} 5 \rightarrow \cancel{1} \underline{2} 3 5 \rightarrow 2 \cancel{3} \underline{5} \rightarrow 1 5$$$; $$$(t_1, t_2, t_3) = (4, 1, 2)$$$.

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

- $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 3 2 5 \rightarrow 4 3 \cancel{2} \underline{5} \rightarrow 4 3 5$$$;
- $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{3} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;
- $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 7 2 5 \rightarrow 4 7 \cancel{2} \underline{5} \rightarrow 4 7 5$$$;
- $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{7} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;

Example input:
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

Example output:
2
0
4

Editorial:
Consider element with index $$$i$$$ that has value $$$b_1$$$ in the array $$$a$$$ — $$$a_i$$$. There are three options:
• Both $$$a_{i-1}$$$ and $$$a_{i+1}$$$ are present in the array $$$b$$$. Then both of them should stay in the array $$$a$$$ after the first operation  — we will write them down later on. However, $$$a_i$$$ can only be added to the array b while removing one of the neighbors. We have reached a contradiction, so the answer is 0.
• One of the numbers $$$a_{i-1}$$$, $$$a_{i+1}$$$ is present in the array $$$b$$$, another is not. Then we have to remove the one that is not present in $$$b$$$ and continue solving the problem.
• Neither $$$a_{i-1}$$$ nor $$$a_{i+1}$$$ is present in $$$b$$$. $$$a_i$$$ is not present in any other place in $$$b$$$ (because all number in $$$b$$$ are unique), and $$$a_{i-1}$$$, $$$a_i$$$ and $$$a_{i+1}$$$ are indistinguishable by the following operations. Let us then remove any one of them (say, left) and "remove" all remaining tags. In this case, we can multiply answer by 2 and continue solving the problem.
Now we know that the answer is either 0 or a power of 2. To calculate the answer we only need to implement the above-mentioned algorithm. Let us store a set of available numbers in the array $$$a$$$, and a set of numbers that are yet to appear in the array $$$b$$$ to implement necessary checks. The solution will have $$$\mathcal{O}(n \log n)$$$ complexity (that can be optimized to $$$\mathcal{O}(n)$$$ with help of arrays and double-linked lists, but it was not necessary for this particular problem).