Kevin and Puzzle (Hard Version)
Contest: Codeforces Global Round 28
Difficulty rating: 3500
Tags: bitmasks, fft, math

This is the hard version of the problem. The difference between the versions is that in this version, you need to count the number of good arrays. You can hack only if you solved all versions of this problem.

Kevin is visiting the Red Church, and he found a puzzle on the wall.

For an array $$$ a $$$, let $$$ c(l,r) $$$ indicate how many distinct numbers are among $$$ a_l, a_{l+1}, \ldots, a_r $$$. In particular, if $$$ l > r $$$, define $$$ c(l,r) = 0 $$$.

You are given a string $$$ s $$$ of length $$$ n $$$ consisting of letters $$$ \texttt{L} $$$ and $$$ \texttt{R} $$$ only. Let a non-negative array $$$ a $$$ be called good, if the following conditions hold for $$$ 1 \leq i \leq n $$$:

- if $$$s_i=\verb!L!$$$, then $$$c(1,i-1)=a_i$$$;
- if $$$s_i=\verb!R!$$$, then $$$c(i+1,n)=a_i$$$.

You need to count the number of good arrays $$$a$$$. Since the answer may be large, you only need to output the answer modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of string $$$s$$$.

The second line of each test case contains a string $$$s$$$ with a length $$$n$$$, containing only English uppercase letters $$$\verb!L!$$$ and $$$\verb!R!$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output the number of good arrays modulo $$$998\,244\,353$$$.

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

Note:
All arrays satisfying the conditions can be found in the easy version of this problem.

Example input:
4
3
LLR
3
RRL
4
RRLR
5
LLRLR

Example output:
1
2
0
1

Editorial:
Hint #1: Only the case where the characters on both sides are RL in the simple version needs to be counted. In fact, the numbers at these two positions, RL, must be the same.
Hint #2: Let the number at the RL positions be $$$m$$$, and enumerate the rightmost R position $$$x$$$ that is filled with $$$m$$$, and the leftmost L position $$$y$$$ that is filled with $$$m$$$.
Hint #3: The case where $$$x > y$$$ is easy to resolve. For the case where $$$x < y$$$, analyze the necessary and sufficient conditions for it to hold.
Hint #4: For the final transformed condition, use bitset or convolution to complete the counting.
According to the easy version, we can see that most cases have very few solutions because for LR, LL, and RR, after filling in the inner part, the outer layer only has one unique way to fill. Therefore, if there is no RL layer, the answer must be $$$1$$$.
Next, consider the case where RL is present. Let's assume that RL is the outermost pair of characters.
It can be proved that the numbers at the R and L positions in this RL must be the same. The specific proof is omitted here, but readers can prove this for themselves easily.
Let this common value be $$$m$$$. Then, enumerate the rightmost R position $$$x$$$ filled with $$$m$$$ and the leftmost L position $$$y$$$ filled with $$$m$$$. Now, let's discuss the relationship between $$$x$$$ and $$$y$$$:
• If $$$x > y$$$, it can be observed that all L's to the right of $$$x$$$ must be filled with $$$m$$$, and all R's to the right of $$$x$$$ have only one way to be filled. The same applies for $$$y$$$. For this case, we can directly enumerate $$$m$$$, then determine the unique positions for $$$x$$$ and $$$y$$$, and check if $$$x > y$$$.
• 
Finally, we only need to count the cases separately. The case where $$$x > y$$$ can be counted in $$$O(n)$$$, for the case where $$$x < y$$$, without loss of generality, assume $$$a \ge b$$$, we can enumerate $$$y$$$, calculate the length of the longest consecutive R's before $$$y$$$, denoted as $$$cnt$$$, so the restriction on $$$a$$$ becomes $$$b \le a \le b + cnt$$$.
• When $$$cnt = 0$$$, the value of $$$a$$$ is fixed, but the corresponding $$$x$$$ can be chosen from any position in a consecutive block of R's. We find that because $$$cnt = 0$$$, i.e., the position before $$$y$$$ is filled with L, then the position after $$$x$$$ cannot be filled with R, so $$$x$$$ can only be chosen as the last R in the consecutive R block.
• When $$$cnt > 0$$$, we only need to enumerate the values of $$$x$$$. It is easy to see that each $$$x$$$ will be counted at most $$$2$$$ times.
Through the above observations, we only need to enumerate $$$O(n)$$$ pairs of $$$x$$$ and $$$y$$$ and check whether they increase the answer by $$$1$$$. That is, the answer is at the $$$O(n)$$$ level.
The last problem is: for each given interval $$$[l, r]$$$, we need to check if there is any RL situation when taking the first and last characters of this string.
A simple solution is to use a bitset to maintain, for example, by scanning $$$r$$$ from small to large, and maintaining the existence of RL for each $$$l + r$$$. The time complexity of this approach is $$$O(\frac{n^2}{\omega})$$$, which can be handled by this problem.
If using block convolution, a more optimal complexity can be achieved. In fact, if further exploring the properties, the time complexity can be reduced to $$$O(n \log^2 n)$$$ (requiring convolution), which you can explore on your own if you are interested.