Problem Statement

The Kingdom of yuki has $N$ towns. In the Kingdom of yuki, the season differs from town to town, and the season of the $i$-th town is represented by $S_i$. If $S_i$ is U, the town is in summer; if F, autumn; if W, winter; and if P, spring.

The $i$-th town has $A_i$ one-way doors. Using one door, you can warp to one specific other town in the Kingdom of yuki.

Now, consider visiting a total of 4 towns by first choosing one town to visit, and thereafter repeatedly warping through one of the doors in the current town. Here, you move from the $j$-th visited town $(j =1,2,3)$ to the $j+1$-th visited town with $1$ warp. No means of travel other than warping through doors can be used.

You want the seasons of the 4 visited towns to be, in the order of visiting, "summer → autumn → winter → spring".

There are $(N-1)^{A_{all}}$ combinations of door destinations in total (where $A_{all}$ is the total number of doors). Over all of them, find the sum of the number of ways of visiting towns such that the seasons of the visited towns are "summer → autumn → winter → spring", modulo $998244353$.

Two ways of visiting towns are distinguished if there exists some $j(1 \leq j \leq 4)$ such that the $j$-th visited town differs. Note that ways of visiting towns in which the $j$-th visited town is the same for all $j(1 \leq j \leq 4)$ are not distinguished, even if the doors used for moving differ.

Constraints

• $2 \leq N \leq 3 \times 10^5$
• $S_i$ is one of U, F, W, P.
• $1 \leq A_i \leq 10^5$
• $N, A_i$ are integers.

Input

The input is given from Standard Input in the following format.

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

Output

Output the answer.

Sample

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