Two Permutations

There are two permutations $P_1,P_2,\dots,P_n$, $Q_1,Q_2,\dots,Q_n$ and a sequence $R$. Initially, $R$ is empty. While at least one of $P$ and $Q$ is non-empty, you need to choose a non-empty array ($P$ or $Q$), pop its leftmost element, and attach it to the right end of $R$. Finally, you will get a sequence $R$ of length $2n$.

You will be given a sequence $S$ of length $2n$, please count the number of possible ways to merge $P$ and $Q$ into $R$ such that $R=S$. Two ways are considered different if and only if you choose the element from different arrays in a step.

The first line contains a single integer $T$ ($1 \leq T \leq 300$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1 \leq n \leq 300\,000$), denoting the length of each permutation.

The second line contains $n$ distinct integers $P_1,P_2,\dots,P_n$ ($1\leq P_i\leq n$).

The third line contains $n$ distinct integers $Q_1,Q_2,\dots,Q_n$ ($1\leq Q_i\leq n$).

The fourth line contains $2n$ integers $S_1,S_2,\dots,S_{2n}$ ($1\leq S_i\leq n$).

It is guaranteed that the sum of all $n$ is at most $2\,000\,000$.

For each test case, output a single line containing an integer, denoting the number of possible ways. Note that the answer may be extremely large, so please print it modulo $998\,244\,353$ instead.

2
3
1 2 3
1 2 3
1 2 1 3 2 3
2
1 2
1 2
1 2 2 1

2
0

2022“杭电杯”中国大学生算法设计超级联赛（3）