문제
고고학자인 재환이는 최근 농부 우현이로부터 오래된 고문서를 넘겨받았다. 이제껏 본적이 없는 아주 흥미로운 문서였는데, 이 문서는 C, O, W 세 개의 문자로만 이루어져 있었다. 오랜 시간 해독하던 재환이는 문장 중에 COW를 만들 수 있는 경우가 얼마나 될지 세어 보기로 하였다. 문자열 COW의 순서는 유지하되 연속적이지는 않아도 가능한 경우의 수에 포함시켰다. 예를 들어 CWOW 에서는 한 가지, CCOW 에서는 두 가지, CCOOWW는 여덟 가지 방법으로 COW가 등장한다.
고문서의 어떤 페이지에서는 문자열이 길지 않아 쉽게 셀 수 있었지만 다른 페이지의 문자열은 100자 이상인 경우도 있었고 심지어 10만자나 되는 페이지도 있어서 도저히 손으로 세는 것은 불가능 하였다.
재환이는 프로그래머인 당신에게 이 문제에 대한 도움을 요청하고 있다. 재환이의 요청에 답을 구하는 프로그램을 작성해보자.
입력
첫 행에 문자열의 길이 N (1 ≤ N ≤ 100,000)이 입력된다.
다음 행에 대문자로 이루어진 문자열이 입력된다.
출력
문자열 COW가 등장하는 경우의 수를 출력한다.
문자열 COW가 연속할 필요는 없다.
경우의 수가 int범위를 초과할 수 있다.
예제
6
COOWWW
6
출처
USACO February 2015 Bronze
로그인해야 코드를 작성할 수 있어요.