COW#11177
Bessie the cow has stumbled across an intriguing inscription carved into a large stone in the middle of her favorite grazing field. The inscription appears to be written in a cryptic ancient language whose alphabet consists of only three characters: , and . Although Bessie cannot decipher the text, she does appreciate the fact that , and , when written in sequence, form her favorite word. She wonders how many times appears in the inscription.
Bessie does not mind if other characters are interspersed between the letters of ; she only requires that the letters appear in the correct order. She also allows different occurrences of to share letters. For example, appears once in , twice in , and eight times in CCOOWW.
Given the text of the inscription, please help Bessie count the number of times appears as a subsequence.
The first line contains a single integer n~(n \le 10^5). The second line contains a string of characters, each of which is either , , or .
Print the number of times appears as a subsequence, not necessarily contiguous, in the input string.
Note that the answer can be very large, so be sure to use -bit integers (such as long~long in C++ or in Java) for the calculation.
Example 1