Practice on Toph

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

Find NSUPS

By flash_7 · Limits 2s, 1.0 GB

Given a string $s$, find the number of subsequence in $s$ which forms the word “NSUPS”. A subsequence is a sequence that can be derived from the string $s$ by deleting some characters from it without changing the order of the remaining characters. You have to find the number of subsequences exists in the string $s$ which is equal to “NSUPS”.

For example, let’s say $s$ = “NNSUUPS”. There are total four ways to select a subsequence equal to “NSUPS” from the string $s$. Those subsequences are “N_SU_PS”, “N_S_UPS”, “_NSU_PS” and “_NS_UPS”.

Input

The first line contains an integer $N$ which denotes the length of the string $s$. The second line contains the string $s$ consisting of uppercase English alphabets.

Constraints:

${1 \leq N \leq 1000}$

Output

Print the answer in a single line.

Samples

InputOutput
7
NNSUUPS
4

Discussion