You are given a string $$$s$$$ of length $$$2n$$$, containing $$$n$$$ characters W and $$$n$$$ characters B.
Let's build a graph on $$$2n$$$ nodes. If $$$s_i \neq s_j$$$ for some $$$1 \le i \lt j \le 2n$$$, then there is an edge of weight $$$|i-j|$$$ between nodes $$$i$$$ and $$$j$$$ in this graph. There are no other edges.
Find the number of shortest Hamiltonian cycles in this graph. As this number can be very large, output it modulo $$$998244353$$$.
As a reminder, a Hamiltonian cycle is a cycle that visits each node exactly once. The length of the cycle is equal to the sum of the weights of its edges. Two cycles are called different if there is an edge that one contains and the other doesn't.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 10^6)$$$.
The second line of each test case contains a string $$$s$$$ of length $$$2n$$$, containing $$$n$$$ characters W and $$$n$$$ characters B.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output the number of shortest Hamiltonian cycles in this graph, modulo $$$998244353$$$.
32WWBB3WBWBWB7WWWWBWBBWWBBBB
1 2 62208
In the first test case, the graph has $$$4$$$ edges: $$$(1, 3)$$$ with weight $$$2$$$, $$$(1, 4)$$$ with weight $$$3$$$, $$$(2, 3)$$$ with weight $$$1$$$, and $$$(2, 4)$$$ with weight $$$2$$$.
There is a unique Hamiltonian cycle here: $$$1 \to 3 \to 2 \to 4 \to 1$$$ (Note that, for example, cycle $$$1 \to 4 \to 2 \to 3 \to 1$$$ contains the same set of edges, so we have already counted it).
