스위트콘 찾기

문제

SW-IT CONTEST는 ‘스위트콘테스트’라고 읽힌다. 그래서 이 대회의 테마는 스위트콘이다.

길이가 $N$인 문자열 $S$가 주어진다. 이 문자열에서 switcon이 되는 *부분 수열의 개수를 구해 보자.

*부분 수열은 문자열에서 몇 개의 문자를 골라 원래 순서대로 이어 붙인 문자열이다. 고른 문자의 위치가 다르면 서로 다른 경우로 센다.

입력

첫째 줄에 문자열의 길이 $N$이 주어진다. $(1 \le N \le 1,000,000)$

둘째 줄에 영문 소문자로 이루어진 길이가 $N$인 문자열 $S$가 주어진다.

출력

switcon이 되는 부분 수열의 개수를 $1,000,000,007$로 나눈 나머지를 출력한다.

예제 1

11
switcontest

출력 1

1

예제 2

9
sswitccon

출력 2

4

힌트

문자열 s와 c가 각각 2개씩 있으므로, 다음과 같이 문자의 위치(인덱스)를 다르게 골라 총 4가지 방법으로 switcon을 만들 수 있다.

• 첫 번째 s와 첫 번째 c 선택: $\underline{\text{s}}\text{s}\underline{\text{wit}}\underline{\text{c}}\text{c}\underline{\text{on}}$
• 첫 번째 s와 두 번째 c 선택: $\underline{\text{s}}\text{s}\underline{\text{wit}}\text{c}\underline{\text{c}}\underline{\text{on}}$
• 두 번째 s와 첫 번째 c 선택: $\text{s}\underline{\text{s}}\underline{\text{wit}}\underline{\text{c}}\text{c}\underline{\text{on}}$
• 두 번째 s와 두 번째 c 선택: $\text{s}\underline{\text{s}}\underline{\text{wit}}\text{c}\underline{\text{c}}\underline{\text{on}}$

예제 3

8
swittest

출력 3

0

힌트

문자열에 c와 o 등이 포함되어 있지 않아 switcon을 만들 수 있는 부분 수열이 존재하지 않는다.