문자열의 개수

길이가 L인 문자열 S가 주어진다. 임의의 문자열 T에 대해 c(T)를 T 안에서 S가 서로 겹치지 않게 등장하는 최대 횟수로 정의한다. 이때 S를 이루는 문자는 T 안에서 연속으로 나타나야 한다.

예를 들어 S = "ab"이면 c("xyz") = 0, c("ababxab") = 3이다. S = "aaa"이면 c("aa") = 0, c("aaaaaa") = 2이다.

두 정수 N과 K가 주어질 때, 다음 세 조건을 모두 만족하는 문자열 X의 개수를 구하는 프로그램을 작성하시오.

• X는 알파벳 소문자로만 이루어진다.
• X의 길이는 $L \times K$ 이상 $L \times K + N$ 이하이다.
• c(X) = K이다.

K = 0이면 길이가 0인 X도 조건을 만족한다. 빈 문자열의 c 값은 0이므로 이 문자열도 개수에 포함한다.

첫째 줄에 문자열 S와 정수 N, K가 공백으로 구분되어 주어진다.

S는 알파벳 소문자로만 이루어져 있고 길이는 L이다. ($1 \le L \le 100$, $0 \le N \le 1000$, $0 \le K \le 10^9$)

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

S = "xy", N = 2, K = 1인 경우를 보자. 길이가 4이면서 "xy"를 한 번 이상 포함하는 문자열은 2027개인데, 그중 "xyxy"는 c 값이 2이므로 제외해야 하고 2026개가 남는다. 길이가 3인 문자열은 52개, 길이가 2인 문자열은 1개이므로 답은 2079이다.

S = "q", N = 2, K = 1인 경우에는 q를 정확히 하나만 포함하는 문자열이 답이 된다. 길이가 1인 문자열은 1개, 길이가 2인 문자열은 $2 \times 25 = 50$개, 길이가 3인 문자열은 $3 \times 25^2 = 1875$개다.