Comet OJ

C1184 [Contest #1]牛吃草问题 +2

内存限制：256 MB 时间限制：2000 ms

题目描述

AA 家有个后院，这个后院实际上是一条笔直的通道，我们可以把它抽象成直线，并且把每个位置用整数编号，共有 $2 \times N + 1$ 个位置，从左到右依序编号为 $1 \sim 2 \times N + 1$。

AA 在所有的奇数位置上，都种了一株草，而在某些偶数位置上，各圈养了一头牛。(一个位置至多养一头牛)

到了吃饭时间时，所有牛会被按照某个顺序放出来吃草，一只牛吃饱回家后，下一只牛才会被放出来。

每头牛都有自己的喜好方向，在被放出来吃草的时候，它会朝自己的喜好方向前进，直到遇到第一株还没被吃掉的草，停下来吃掉它后再心满意足地走回自己的家中。

现在给你每一头牛的喜好方向，以及吃饭时间结束后每个位置的草是否被吃掉 (尚未重新长出草之前)，请你计算出这些牛被放出去吃草的顺序有多少种可能。

两种顺序被视为不同当且仅当至少存在某两头牛 $x$ 和 $y$，在其中一种顺序是 $x$ 比 $y$ 先被放出来，但在另一种顺序是 $y$ 比 $x$ 先被放出来。

请参考提示中的样例解释能帮助你更了解题意。

注 1：有办法证明，无论牛的释放顺序是什么，都一定有草吃。

注 2：每个奇数位置的草地在一餐全部的牛吃完之后到下一餐第一只牛放出来之前，会全部长回来唷！

输入格式

第一行有一个正整数 $T$ ($T \le 10^5$)，代表有几组数据。

接着每组数据的第一行有一个正整数 $N$ ($1 \le N \le 10^5$) 代表 AA 家后院的大小。第二行有一个长度为 $2 \times N + 1$ 的字符串，其中偶数位置的字符若是 '.'，代表该位置没有养牛；若是 'L'，代表该位置养了一头喜好方向是朝左的牛；若是 'R'，代表该位置养了一头喜好方向是朝右的牛。而奇数位置的字符若是 '.'，代表该位置的草在全部牛吃饱后是被吃光光的；否则会是 '#'，代表该位置的草从没被吃掉。

所有数据中 $N$ 的总和不超过 $2 \times 10^6$。

输出

对于每组数据，输出一行包含一个非负整数，代表答案除以 $998244353$ 的余数。

样例

样例输入 1

5
1
#.#
2
.L.L#
2
.R.L#
3
.L.L.L#
1
#L#

样例输出 1

1
2
1
6
0

提示

样例里第一行的 $5$ 代表有五组数据。

第一组数据没有养任何牛，位置 $1$ 和 $3$，在用餐时间过后仍长满草。虽然没有养任何牛，但可能顺序也算是有一种。

第二组数据用餐完后位置 $1$ 和位置 $3$ 的草都被吃光了，并且养了两头牛分别在位置 $2$ 和 $4$，喜好方向都是朝左，无论是先释放位置 $2$ 或是位置 $4$ 的牛，位置 $2$ 的牛总是吃到位置 $1$ 的草，而位置 $4$ 的牛总是吃到位置 $2$ 的草。可能顺序有两种。

第三组数据用餐完后位置 $1$ 和位置 $3$ 的草都被吃光了，并且养了两头牛分别在位置 $2$ 和 $4$，喜好方向分别是朝左和朝右，若先释放位置 $2$ 的牛，它会吃光位置 $3$ 的草，而位置 $4$ 的牛再去吃光位置 $1$ 的草，满足数据给的结果。但若是先释放位置 $4$ 的牛，它会吃光位置 $3$ 草，而位置 $2$ 的牛就会因此越过位置 $3$，改去吃光位置 $5$ 的草，和数据给的结果不同。故此数据的可能顺序只有一种。