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

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

보통6동적 계획법문자열 매칭아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

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

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

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

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

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