Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Halting Assembly

By upobir · Limits 1.5s, 512 MB

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 998244353998244353

Input

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

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

1n21051 \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 998244353998244353

Samples

InputOutput
5
NNJJN
3
InputOutput
10
NNJNNJJNJN
348

    Discussion

    Statistics


    90% Solution Ratio

    hitonanodeEarliest, 2w ago

    Apurba.884537Fastest, 0.1s

    serotoninLightest, 4.1 MB

    serotoninShortest, 2546B

    Submit

    Login to submit

    Editorial

    If we compress all blocks of ‘N’ then for the assembly to halt, the program jumps from one block to ...

    Related Contests