CF2048I2.Kevin and Puzzle (Hard Version)

这是此题目的困难版本，两个版本的区别在于在这个版本中，你需要计算出所有“好数组”的数量。只有在解决了所有版本的问题后，才可以进行 hack。

Kevin 在参观红教堂时发现了一道墙上的谜题。

对于一个数组 $a$，令 $c(l, r)$ 表示数组 $a$ 从位置 $l$ 到 $r$ 的所有元素中，不同数字的个数。特别地，当 $l > r$ 时，定义 $c(l, r) = 0$。

现给定一个长度为 $n$ 的字符串 $s$，该字符串仅由字母 $\texttt{L}$ 和 $\texttt{R}$ 组成。将一个非负整数数组 $a$ 称为“好数组”，如果对于每个 $1 \leq i \leq n$ 满足以下条件：

• 若 $s_i = \verb!L!$，则 $c(1, i-1) = a_i$；
• 若 $s_i = \verb!R!$，则 $c(i+1, n) = a_i$。

你的任务是计算这样的“好数组” $a$ 的数量。由于结果可能会非常大，输出结果时只需对 $998\,244\,353$ 取模。

输入包含多组测试用例。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例中：

• 第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示字符串 $s$ 的长度。
• 第二行是一个长度为 $n$ 的字符串 $s$，由字母 $\verb!L!$ 和 $\verb!R!$ 组成。

并且，所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出“好数组”的数量，并对 $998\,244\,353$ 取模。

本翻译由 AI 自动生成