부분 문자열을 포함하는 문자열의 개수

시간 제한2초메모리 제한512 MB

요약

주어진 단어 S를 연속된 부분 문자열로 포함하는 길이 L의 소문자 문자열 개수를 1,000,000,009로 나눈 나머지를 구합니다.

문제

알파벳 소문자로 이루어진 단어 $S$ 가 주어진다. 길이가 $L$ 이고 알파벳 소문자로만 이루어졌으며 $S$ 를 부분 문자열로 갖는 문자열이 몇 개인지 세는 프로그램을 작성하시오.

부분 문자열은 연속한 구간을 뜻한다.

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

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

첫째 줄에 조건을 만족하는 문자열의 개수를 1,000,000,009로 나눈 나머지를 출력한다.