나는 정말 휘파람을 못 불어
면접 대비시간 제한1초메모리 제한512 MB
문자열 S에서 W, H, E가 순서대로 나오고 E가 두 번 이상 나오는 부분수열의 개수를 10^9+7로 나눈 나머지로 구합니다.
문제
휘파람을 불지 못하는 시루는 휘파람을 불기 위해 수없이 시도하지만 번번이 실패한다. 시루의 휘파람 연습을 돕는 루시는 시루가 휘파람과 비슷한 소리를 낼 때마다 사탕을 하나씩 주기로 했다.
시루의 입에서 나온 소리는 대문자로 구성된 문자열 로 나타낼 수 있다. 루시는 에서 휘파람과 비슷한 소리, 즉 '유사 휘파람 문자열'의 개수를 구해야 한다. '유사 휘파람 문자열'은 다음과 같이 정의한다.
WHEE는 '유사 휘파람 문자열'이다.- '유사 휘파람 문자열' 뒤에
E를 붙인 것도 '유사 휘파람 문자열'이다.
'유사 휘파람 문자열'은 에서 연속할 필요가 없다. 즉, 의 부분 수열 중 '유사 휘파람 문자열'인 것의 개수를 구하면 된다.
시루는 수없이 시도했기 때문에 의 길이가 매우 길어졌다. 루시를 도와 시루에게 사탕을 몇 개 줘야 하는지 계산하자.
입력
첫째 줄에 문자열 의 길이 이 주어진다. 둘째 줄에는 대문자로만 구성된 문자열 가 주어진다.
출력
'유사 휘파람 문자열'인 부분 수열의 개수를 로 나눈 나머지를 출력한다.
제한
- 는 대문자로만 구성되어 있다.