← 返回题目列表

Codeforces · 2048/I2

I2. 凯文和谜题(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,您需要统计好数组的数量。只有解决了该问题的所有版本,您才能破解。

凯文正在参观红教堂,他在墙上发现了一个谜题。

对于数组 $$$ 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

注意

所有满足条件的数组都可以在这个问题的简单版本中找到。