Halting Assembly

Oyler is learning about assembly programming in his class. To explain jump instruction easily, his teacher started with a restricted set of instructions. There are only two instructions in this language: NOP, meaning that do nothing and go to the next instruction in sequence and JMP X, meaning that go to instruction X (1-indexed) that has NOP. So using JMP, you cannot go to another instruction that also has JMP. For example, the following program is a valid program:

NOP
NOP
JMP 5
JMP 1
NOP

This code performs instruction in order 1, 2, 3, 5 (4 is skipped due to jump at 3).

If a program starts from the first instruction and makes it to the last instruction, then it is called a halting program. Note that not all programs will halt. For example, in the above program if we swapped instruction 3 and 4 then the program would not halt.

After finishing teaching all this, the teacher gave the students an interesting assignment. He gave them a program that has incomplete JMP instructions, the X’s (jump targets) of JMP instructions are missing. Students have to count the number of valid assignments of the jump targets such that the final program halts. Two assignments are different if at least one JMP instruction has different jump targets.

Now you have to help oyler do his assignment. Given the program, output the count. Since the count can be large output it modulo $998244353$

Input

The program will be given as a string of length $n$ that consists of character ‘J’ and ‘N’ representing the JMP and NOP instructions. $i$ th character represents the $i$ th instruction.

The first line will contain the length $n$ of the string and second line will contain the $n$ length string consisting of only ‘J’ and ‘N’. The first and last character of the string will be N.

$1 \leq n \leq 2 \cdot 10^5$

Output

Output the count of ways to assign target instructions to JMP instructs such that the program halts. Output the count modulo $998244353$

Samples

Input	Output
5 NNJJN	3

Input	Output
10 NNJNNJJNJN	348