/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 人が円卓に座っており，各人は反時計回りに順に 1, \ldots, N と番号付けられています．各人はそれぞれ左右どちらか一方の利き手を持っています．
円卓上には 1, \ldots, N と番号付けられた計 N 本のスプーンが，隣り合う二人の間に 1 本ずつ置いてあります．各 1 \leq i \leq N について，人 i の左側，右側にはそれぞれスプーン i，スプーン (i+1) があります．ここで，スプーン (N+1) はスプーン 1 のことを指します．
N = 4 での模式図を以下に示します．
(1, \dots, N) の順列 (P_1, \dots, P_N) が与えられます．i=1,\dots,N の順に，人 P_i が以下のように行動します．
- 自分の右側または左側にスプーンが残っているならば，そのうち 1 つを取る．
- このとき自分の両側にスプーンが残っているならば，自分の利き手の側のスプーンを取る．
- そうでないならば何もしない．
L, R, ? からなる長さ N の文字列 S が与えられます．N 人の利き手の組み合わせは 2^N 通りありますが，そのうち以下の条件を全て満たすような組み合わせの数を 998244353 で割った余りを求めてください．
- S の i 番目の文字が
Lならば，人 i は左利きである． - S の i 番目の文字が
Rならば，人 i は右利きである． - 全員の行動が終了したとき，全員がスプーンを取っている．
制約
- 入力される数値は全て整数
- 2 \leq N \leq 2 \times 10^5
- (P_1, \dots, P_N) は (1, \dots, N) の順列
- S は
L,R,?からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる．
N P_1 \dots P_N S
出力
答えを 1 行に出力せよ．
入力例 1
3 1 2 3 L??
出力例 1
2
人 1,2,3 がそれぞれ左利き，左利き，右利きのとき，以下のように行動が行われます．
- 人 1 が行動を開始する．人 1 の両側にスプーンが残っているので，人 1 の利き手と同じ左側のスプーン 1 を取る．
- 人 2 が行動を開始する．人 2 の両側にスプーンが残っているので，人 2 の利き手と同じ左側のスプーン 2 を取る．
- 人 3 が行動を開始する．人 3 の右側にはスプーンが残っておらず，左側にはスプーン 3 が残っているので，スプーン 3 を取る．全員の行動が終了し，このとき全員がスプーンを取っている．
この利き手の組み合わせは条件を満たします．他には人 1,2,3 がそれぞれ左利き，左利き，左利きの場合も条件を満たします．
入力例 2
3 1 3 2 R?L
出力例 2
0
条件を満たす利き手の組み合わせが存在しません．
入力例 3
12 6 2 9 3 1 4 11 5 12 10 7 8 ????????????
出力例 3
160
Score: 400 points
Problem Statement
N people are sitting around a round table, and numbered 1 to N in a counterclockwise order. Each person has a dominant hand: left or right.
There are N spoons numbered 1 to N on the round table, with one spoon placed between each pair of adjacent people. For each 1 \leq i \leq N, to the left and right of person i, there are spoons i and (i+1), respectively. Here, spoon (N+1) refers to spoon 1.
Below is a diagram for N = 4.
You are given a permutation (P_1, \dots, P_N) of (1, \dots, N). In the order i=1,\dots,N, person P_i will act as follows:
- If there is a spoon remaining on left or right side, they will take one of them.
- If there are spoons remaining on both sides, they will take the spoon on the side of their dominant hand.
- Otherwise, they do nothing.
You are also given a string S of length N consisting of L, R, and ?. Among the 2^N possible combinations of dominant hands, find how many satisfy all of the following conditions, modulo 998244353:
- If the i-th character of S is
L, person i is left-handed. - If the i-th character of S is
R, person i is right-handed. - When everyone has finished acting, everyone has taken a spoon.
Constraints
- All input values are integers.
- 2 \leq N \leq 2 \times 10^5
- (P_1, \dots, P_N) is a permutation of (1, \dots, N).
- S is a string of length N consisting of
L,R, and?.
Input
The input is given from Standard Input in the following format:
N P_1 \dots P_N S
Output
Print the answer in a single line.
Sample Input 1
3 1 2 3 L??
Sample Output 1
2
When persons 1, 2, and 3 are left-handed, left-handed, and right-handed, respectively, the actions are performed as follows:
- Person 1 starts acting. There are spoons on both sides, so person 1 takes spoon 1 on the left side, which is the same as their dominant hand.
- Person 2 starts acting. There are spoons on both sides, so person 2 takes spoon 2 on the left side, which is the same as their dominant hand.
- Person 3 starts acting. There is no spoon on the right side, but spoon 3 is remaining on the left side, so they take spoon 3. Everyone has finished acting and taken a spoon.
This combination of dominant hands satisfies the conditions. Besides, the conditions are also satisfied when persons 1, 2, 3 are all left-handed.
Sample Input 2
3 1 3 2 R?L
Sample Output 2
0
No combinations of dominant hands satisfy the conditions.
Sample Input 3
12 6 2 9 3 1 4 11 5 12 10 7 8 ????????????
Sample Output 3
160