Jumping Frog

Time limit: 1000 msMemory limit: 256 MB

There is a frog at position $0$ in a lake. The frog wants to get to position $N$ .

To do that, it can jump some number of times in the positive direction. For example, if $N = 5$ , the frog could jump like this:

0 \to 3 \to 5

However, only some positions of the lake have lily pads, and the frog can only jump to positions with lily pads.

Additionally, each jump tires the frog, so the distance of the next jump has to be strictly less than the distance of the last jump.

For example, some valid sequences of jump distances are $(3, 2)$ , $(9, 4, 1)$ and $(5)$ , while the sequence of jump distances $(8, 4, 4, 1)$ is invalid, since it is not strictly decreasing.

Positions $0$ and $N$ have lily pads.

Your task is to count in how many ways the frog could get to position $N$ while satisfying the above rules.

Input

The first line of input contains a single integer $N$ ( $2 \le N \le 5000$ ).

The second line contains a string of length $N - 1$ , describing the lake. Each character is either . or L. If the $i$ -th character of the string is , it means position has a lily pad, otherwise it does not.

Output

Output a single integer: the number of ways the frog could get to position $N$ . Since this number may be large, output it modulo $998244353$ .

Samples

Sample 1

Input

5
..L.

Output

There are two ways to get to $5$ : $0 \to 5$ and $0 \to 3 \to 5$ .

Sample 2

Input

6
.....

Output

The only way is $0 \to 6$ .

Jumping Frog

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3