Cheating and Stealing

题号：NC222401
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Gromah is playing PingPong with PJ King. However, Gromah is poor at PingPong and it's difficult for him to beat PJ King in the normal way. So Gromah has to cheat and steal, which is to let PJ King send some points and then change the winning points in one game after the end of the match.

Gromah and PJ King have played $n_{}$ times totally, and the results were all recorded as a string $S_{}$ only containing "W"(denoting Gromah wins this point) and "L"(denoting PJ King wins this point). Now Gromah wants to know that for all $i \in \{1, 2, \cdots, n\}$ , how many games he can win if the winning point equals $i_{}$ in one game(denoted by $f_i(S)$ ), and you can determine $f_i(S)$ in following procedure:

(1). Check if there is any prefix in current $S_{}$ satisfying $\max(cnt_W, cnt_L) \ge i, |cnt_W - cnt_L| \ge 2$ where $cnt_W, cnt_L$ denotes the number of "W"s and "L"s in the prefix respectively.
(2). If no such prefix exists, terminate the procedure regardless of the remaining results.
(3). If exists, choose the shortest prefix among all valid prefixes(denoting one game), and add 1 to $f_i(S)$ iff $cnt_W > cnt_L$ . Then remove the chosen prefix from $S_{}$ and turn back to step (1).

Since the output is too large, you should only print one integer $\sum_{i=1}^{|S|} f_i(S) \times (|S| + 1)^{i-1} \pmod{998244353}$ .

输入描述:

The first line contains one integer , denoting the length of the string .

The second line contains one string  of length , which only contains "W" and "L".

输出描述:

Output one line containing only one integer, denoting the answer.

示例1

输入

复制

9
LWWWLLWLL

输出

复制

说明

, Gromah wins one game("LWWW"), then PJ King wins one game("LL"), and "WLL" remains.
, Gromah wins one game("LWWW"), then PJ King wins one game("LL"), and "WLL" remains.
, Gromah wins one game("LWWW"), then PJ King wins one game("LLWL"), and "L" remains.
, no game finished.

So the answer equals .