Bessie has stumbled across an inscription carved into a large stone, written in a cryptic ancient language with an alphabet of only the three characters C, O, and W. She wonders how many times COW appears in the text.

Bessie doesn't mind if there are other characters interspersed within COW, only that the characters appear in the correct order. She also doesn't mind if different occurrences of COW share some letters. For instance, COW appears once in CWOW, twice in CCOW, and eight times in CCOOWW.

Given the text of the inscription, please help Bessie count how many times COW appears as a (not necessarily contiguous) subsequence.

Line 1: a single integer N <= 10^5. Line 2: a string of N characters, where each character is C, O, or W.

The number of times COW appears as a subsequence of the input string. The answer can be very large, so use 64-bit integers.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > February > Bronze