26156번 - 나락도 락이다

문제

나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.?

알파벳 대문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$의 부분열 중 ROCK으로 끝나는 문자열의 개수를 10ドル^9+7$로 나눈 나머지를 출력하라.

입력

첫 번째 줄에 문자열 $S$의 길이 $N$이 주어진다. $(4 \leq N \leq 1\ 000\ 000)$

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$가 주어진다.

출력

$S$의 부분열 중 ROCK으로 끝나는 문자열의 개수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.

제한

노트

문자열의 부분열이란 문자열에서 몇몇 문자를 지운(물론 지우지 않아도 된다) 문자열을 의미한다. 예를 들어 aan은 hanyang의 부분열이다.