题目描述

有 $n$ 个人从左到右排成一列，至少有一人是恶人。每个人都会说，离自己最近的恶人在左边还是右边；如果左右两边最近的恶人距离相同，他必须说左边。恶人本人说左边或右边均可。

给定一个长度为 $n$ 的字符串 $s$。字符 L 或 R 表示这个人的说法已经确定，字符 ? 表示他的说法可以任选 L 或 R。

求可能的情况数。两种情况不同，当且仅当至少一人的身份不同，或至少一人的实际说法不同。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $s$，其中每个字符均为 L、R 或 ?。

输出格式

输出一个整数，表示可能的情况数对 $998244353$ 取模的结果。

数据范围

$1\le n\le 5\times 10^5$。

子任务

样例 1

3
L??

9

样例 1 说明

可行的恶人位置集合为 $\{1\}$、$\{1,2\}$、$\{1,3\}$、$\{1,2,3\}$，贡献分别为 $1,2,2,4$，总计 $9$。

样例 2

5
?LR??

57