시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 22 11 10 66.667%

문제

알파벳 소문자로 이루어진 단어 S가 주어졌을 때, 길이가 L이면서 S를 부분 문자열로 갖는 알파벳 소문자로만 이루어진 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 길이 L (1 ≤ L ≤ 100)이 주어진다.

둘째 줄에 단어 S가 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 길이가 L이면서 S를 부분 문자열로 갖는 알파벳 소문자로만 이루어진 문자열의 개수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력

4
abc

예제 출력

52

예제 입력 2

4
aaa

예제 출력 2

51

예제 입력 3

4
aaaa

예제 출력 3

1

힌트

출처