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 (1 ≤ N ≤ 1000) which denotes the length of the string s. The second line contains the string s consisting of uppercase English alphabets.

Output

Print the answer in a single line.

Sample

InputOutput
7
NNSUUPS
4

Discussion

Statistics


82% Solution Ratio

PsychoKillerEarliest, Dec '18

PsychoKillerFastest, 0.0s

touhidurrrLightest, 0 B

bokaifShortest, 121B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.