美好的梦境（一）

Problem Description

本题与 美好的梦境（二）的区别将使用【全角中括号】标注。

又是空虚的一天，老师已经不知道这是第几次了。看着眼前作为值日生的 Serika，他始终无法忘记她上一次的遭遇。千千万万不要重蹈上一位的覆辙，老师自思道。Serika 注意到了老师的心思，她决定通过美好的梦境来帮助他重整旗鼓。 老师有 $n$ 个关于学生的梦境，编号为 $1,2,3,\cdots,n$。它们作为节点构成了一棵有根树。编号为 $i$（$1\le i\le n$）的梦境拥有 $k_i$ 个儿子梦境，编号分别为 $p_{i,1},p_{i,2},p_{i,3},\cdots,p_{i,k_i}$。 【现在，对于每个编号为 $i$（$1\le i\le n$）的梦境，老师均会从所有 $[1,k_i]$ 的排列中 等概率随机 选择一个，记为 $a_{i,1},a_{i,2},a_{i,3},\cdots,a_{i,k_i}$。】 老师认为：

1. 编号为 $p_{i,a_{i,j}}$（$1\le i\le n$，$1\le j\le k_i$）的非根梦境的 左梦境 为编号为 $p_{i,a_{i,\max(j-1,1)}}$ 的梦境， 右梦境 为编号为 $p_{i,a_{i,\min(j+1,k_i)}}$ 的梦境。（根据定义，一个非根梦境的左梦境或右梦境均可以是它本身）
2. 编号为 $i$（$1\le i\le n$）的非叶子梦境的 真儿子梦境 为编号为 $p_{i,a_{i,1}}$ 的梦境。 为了帮助老师重新品味这些梦境，Serika 从 Koyuki 手里购买了三种 Millennium Science School 监制的梦境转移器，分别记作 ←、→ 和 ↓。通过阅读说明书，老师得知了执行这三种梦境转移器所产生的效果：
3. 转移器 ← 的效果是：若当前所处梦境是根梦境， 不移动 ，否则移动至它的左梦境。
4. 转移器 → 的效果是：若当前所处梦境是根梦境， 不移动 ，否则移动至它的右梦境。
5. 转移器 ↓ 的效果是：若当前所处梦境是叶子梦境， 不移动 ，否则移动至它的真儿子梦境。 【老师现在处于根梦境，他会依照某种顺序执行这些转移器。这个顺序将以字符串的形式给出，具体内容见 输入/输出格式。他找来了你帮忙计算他最终移动到的梦境编号的期望值，对 $998244353$ 取模。】

Input

本题包含多组测试数据。 首先在第一行输入一个整数 $T$（$1\le T\le10$）表示测试数据组数。 对于每一组测试数据，输入包含 $n+2$ 行。 第一行包含一个整数 $n$（$1\le n\le 300$）表示梦境的数量。 第二行包含一个仅出现 L、R、D 字符的字符串 $S$（$1\le |S|\le 300$）表示转移器执行的顺序。字符 L 表示此时执行转移器 ←，字符 R 表示此时执行转移器 →，字符 D 表示此时执行转移器 ↓。 接下来 $n$ 行，第 $i+2$（$1\le i\le n$）行首先包含一个整数 $k_i$（$0\le k_i\lt n$）表示梦境 $i$ 的儿子梦境个数。接下来包含 $k_i$ 个整数 $p_{i,1},p_{i,2},p_{i,3},\cdots,p_{i,k_i}$（$1\le p_{i,1},p_{i,2},p_{i,3},\cdots,p_{i,k_i}\le n$），表示梦境 $i$ 的儿子梦境。 保证输入的梦境构成一棵有根树。

Output

对于每一组测试数据，输出包含一行一个整数表示期望值对 $998244353$ 取模后的值。

Sample Input

2
4
DLRLDR
2 2 3
0
1 4
0
10
LRLLDLRRLLDLDDDLLRLD
3 2 3 4
0
0
2 5 6
2 8 9
1 7
0
0
1 10
0

Sample Output

499122180
332748122

Hint

在样例的第一组测试数据中，讨论以下两种情况：

1. $a_{1,1}=1,a_{1,2}=2$，此时最终移动到编号为 $3$ 的梦境。
2. $a_{1,1}=2,a_{1,2}=1$，此时最终移动到编号为 $4$ 的梦境。 综上，答案为 $\frac{7}{2}$，对 $998244353$ 取模后为 $499122180$。 样例的第二组测试数据的答案为 $\frac{13}{3}$，对 $998244353$ 取模后为 $332748122$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）