题目描述

小 W 有一个长度为 $2n$（$n$ 为偶数）的指令序列 $S$，其中包含 $\tt L$, $\tt R$ 两种指令，其中 $\tt L$ 表示往数轴负方向走 1 个单位，$\tt R$ 表示往数轴正方向走 1 个单位。

小 W 和小 B 会依据指令序列 $S$ 在数轴上进行一个有趣的游戏，该游戏的具体流程如下：

• 初始时，小 W 出现在数轴原点。
• 接下来 $n$ 步，小 W 会按照 $S_1, S_2, \dots, S_n$ 的指令内容依次执行。
• $n$ 步后，小 B 会出现在原点（注意此时若小 W 也在原点也认为二者在此时相遇），接下来第 $n+1$ 步至 $2n$ 步，第 $n+k$（$1 \le k \le n$）步时小 W 会按照 $S_{n+k}$ 的指令内容行动一步，同时小 B 会按照 $S_k$ 的指令内容行动一步。若在第 $n+k$（$k = 0, 1, \dots, n$）步行动后，小 B 和小 W 出现在同一位置，则认为二者在此时相遇。
• 共 $2n$ 步执行完毕后，游戏结束。

若依据该指令序列 $S$ 执行完整整个游戏后，小 W 和小 B 从未相遇，则称该指令序列 $S$ 是合法的。

现在，你得到了一个长度为 $2n$ 的序列 $T$，其除了 $\tt L$, $\tt R$ 两种字符之外，还包含 $\tt ?$ 字符。你需要将 $T$ 中每个 $\tt ?$ 字符替换为 $\tt L$ 或者 $\tt R$，由此得到一个指令序列 $S$。你需要求出所有能得到的合法指令序列 $S$ 的数目，由于方案数可能很大，答案请对 $998244353$ 取模。

输入格式

输入第一行包含一个正整数 $n$（$1 \le n \le 50$ 且 $n$ 为偶数）。

输入第二行包含一个长度为 $2n$ 的字符串 $T$，包含 $\tt L$, $\tt R$, $\tt ?$ 三种字符，含义如题目所示。

输出格式

输出一行一个整数，表示所有合法的指令序列数目对 $998244353$ 取模的结果。

4
L?L?L??R

3

样例解释 1

对于样例中的情况，能得到的合法指令序列数目包括 LLLLLLLR、LRLLLLLR 和 LLLRLLLR 共 $3$ 种情况，故输出 $3$。

数据范围

• 对于 $10\%$ 的数据，$T$ 中没有 $\tt ?$；
• 对于另外 $10\%$ 的数据，$n \leq 8$；
• 对于另外 $20\%$ 的数据，$T$ 只有前半部分可能含有 $\tt ?$；
• 对于另外 $20\%$ 的数据，$T$ 中只有 $\tt ?$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 50$，$n$ 为偶数，$T_i \in \{\tt L, \tt R, \tt ?\}$。