COW

Interview

Time limit1sMemory limit256 MB

Summary

Count the subsequences equal to COW in a string of C, O, and W up to length 100000.

Level: Easy3 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

Bessie the cow found an inscription carved into a large stone in the middle of her favorite grazing field. The text is written in an ancient language whose alphabet has only the three characters C, O, and W. Bessie cannot read the text, but she notices that C, O, and W in that order spell her favorite word, COW, so she wants to know how many times COW appears in the text.

Bessie does not mind other characters sitting between the C, the O, and the W. Only the order matters. She also does not mind when two different occurrences of COW share some letters. For example, COW appears once in CWOW, twice in CCOW, and eight times in CCOOWW.

Given the text of the inscription, count how many times COW appears.

Input

The first line contains an integer $N$ ( $N \le 10^5$ ).

The second line contains a string of $N$ characters, each of which is C, O, or W.

Output

Print the number of times COW appears as a subsequence of the input string. The three letters of the subsequence do not have to be contiguous.

The answer can be very large, so use 64-bit integers for the calculation (long long in C++, long in Java).

Examples4

Example 1
Input
```
6
COOWWW
```
Expected output
```
6
```
Example 2
Input
```
4
CWOW
```
Expected output
```
1
```
Example 3
Input
```
4
CCOW
```
Expected output
```
2
```
Example 4
Input
```
6
CCOOWW
```
Expected output
```
8
```