문제

알파벳 소문자로만 이루어져 있고 길이가 인 문자열 가 주어진다.

다음 조건을 만족하도록 를 1개 이상의 문자열 로 분할하는 경우의 수를 구해라.

• 여야 한다. 즉, 을 순서대로 모두 이어붙이면 가 되어야 한다.
• 모든 에 대해 (이때, 는 의 길이를 의미한다)
• 각 문자열은 모두 aloha를 부분 수열으로 가져야 한다. 즉, 모든 에 대해 에서 문자 몇 개를 지워 aloha를 만들 수 있어야 한다.

입력

첫째 줄에 문자열의 길이 이 주어진다.

둘째 줄에 알파벳 소문자로만 이루어진 문자열 가 주어진다.

출력

첫째 줄에 문제의 정답을 출력해라. 단, 정답이 너무 커질 수 있으므로 로 나눈 나머지를 출력해라.

노트

네 번째 예제처럼 가 "alohaisalcoholgoat"인 경우,

를 {"aloha", "isalcoholgoat"} 혹은 {"alohai", "salcoholgoat"} 혹은 {"alohaisalcoholgoat"}로 위 조건을 만족하면서 나눌 수 있다.

하지만 를 {"aloh", "aisalcoholgoat"} 혹은 {"aloha", "isalcoholgoa", "t"} 처럼 나눈 경우 각각 "aloh"와 "t"를 "aloha"로 만들 수 없기 때문에 문제의 조건을 만족하지 않는다.