这是问题的困难版本。版本之间的区别在于,在这个版本中,您需要统计好数组的数量。只有解决了该问题的所有版本,您才能破解。
凯文正在参观红教堂,他在墙上发现了一个谜题。
对于数组 $$$ a $$$,令 $$$ c(l,r) $$$ 表示 $$$ a_l, a_{l+1}, \ldots, a_r $$$ 中有多少个不同的数字。特别是,如果 $$$ l > r $$$,则定义 $$$ c(l,r) = 0 $$$。
给定一个字符串 $$$ s $$$,长度为 $$$ n $$$,仅由字母 $$$ \texttt{L} $$$ 和 $$$ \texttt{R} $$$ 组成。如果 $$$ 1 \leq i \leq n $$$ 满足以下条件,则称非负数组 $$$ a $$$ 为好数组:
- 如果 $$$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$$$ 的长度。
每个测试用例的第二行包含一个字符串$$$s$$$,长度为$$$n$$$,仅包含英文大写字母$$$\verb!L!$$$和$$$\verb!R!$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出良好数组的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 3 LLR 3 RRL 4 RRLR 5 LLRLR
输出 #1
1 2 0 1
注意
所有满足条件的数组都可以在这个问题的简单版本中找到。