Shugenja

题目描述

There are $n$ people standing in a line, and at least one of them is evil.

Each person has a status: evil or non-evil. Each person also gives a piece of information, saying whether the nearest evil person to them is on their left or on their right. If the nearest evil people on both sides are at the same distance, the person will say "left". In particular, if a person is evil, they may give arbitrary information.

However, the information given by some people is uncertain.

You need to determine the number of possible scenarios. Two scenarios are considered different if and only if there exists at least one person whose status differs, or whose given information differs.

输入格式

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$), denoting the number of people.

The second line contains a string $s$ of length $n$. Each character of $s$ is one of the following:

• L: the person says that the nearest evil person is on their left;
• R: the person says that the nearest evil person is on their right;
• ?: the information given by this person is uncertain.

输出格式

Print a single integer - the answer modulo $998244353$.

样例输入 #1

3
L??

样例输出 #1

9

样例输入 #2

5
?LR??

样例输出 #2

57