問題文

yuki 国には $N$ 個の街があります．yuki 国では，街ごとに季節が異なっており，$i$ 番目の街の季節は $S_i$ で表されます．$S_i$ が U ならばその街は夏，F ならば秋，W ならば冬，P ならば春であることを表します．

$i$ 番目の街には一方通行の扉が $A_i$ 個あり，扉をひとつ用いることで，yuki 国のほかの特定の一つの街にワープできます．

さて，最初にある街を 1 つ選んで訪れ，それ以降は今いる街にある扉のうちどれか一つを用いてワープすることを繰り返すことにより，合計で 4 つの街を訪れることを考えます．ここで，$j$ 番目 $(j =1,2,3)$ に訪れる街から $j+1$ 番目に訪れる街へは，ワープ $1$ 回で移動します．扉によるワープ以外の移動手段を用いることはできません．

このとき，訪れた 4 つの街の季節が，訪れた順に「夏→秋→冬→春」となるようにしたいです．

扉の行先の組合せは全部で $(N-1)^{A_{all}}$ 通りあります（$A_{all}$ は扉の総数）．それらすべてに対する，訪れた街の季節が「夏→秋→冬→春」になるような街の訪れ方の数の総和を $998244353$ で割った余りを求めてください．

なお，街の訪れ方は，ある $j(1 \leq j \leq 4)$ が存在して，$j$ 番目に訪れる街が異なる場合に区別されます．すべての $j(1 \leq j \leq 4)$ に対して，$j$ 番目に訪れる街が同じである街の訪れ方は，移動に用いる扉が異なっても区別されないことに注意してください．

制約

• $2 \leq N \leq 3 \times 10^5$
• $S_i$ は U, F, W, P のいずれかである．
• $1 \leq A_i \leq 10^5$
• $N, A_i$ は整数である．

入力

入力は以下の形式で標準入力から与えられる．

$N$
$S_1$ $A_1$
$S_2$ $A_2$
$\cdots$
$S_N$ $A_N$

出力

答えを出力せよ．

サンプル

4
U 1
F 1
W 1
P 1

3

4
U 3
F 1
W 1
P 1

57

4
P 2017
U 8
F 11
W 16

317248232

16
P 1
U 2
F 3
W 4
P 5
U 6
F 7
W 8
P 9
U 10
F 11
W 12
P 13
U 14
F 15
W 16

958756683