12948번 - 문자열의 개수

문제

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

예를 들어, S = "ab" 인 경우에, c("xyz") = 0, c("ababxab") = 3 이다. S = "aaa"인 경우에는 c("aa") = 0이고, c("aaaaaa") = 2 이다.

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

• X는 알파벳 소문자로 이루어져 있어야 한다.
• X의 길이는 L*K보다 크거나 같고, L*K+N보다 작거나 같아야 한다.
• c(X)의 값은 K가 되어야 한다.

입력

첫째 줄에 문자열 S와 정수 N, K가 주어진다.

S는 알파벳 소문자로만 이루어져 있으며, 길이는 L이다. (0 ≤ N ≤ 1,000, 0 ≤ K ≤ 1,000,000,000, 1 ≤ L ≤ 100)

출력

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

제한

힌트

예제 1의 경우에 길이가 4인 문자열의 개수는 2027개가 있고, 길이가 3인 문자열은 52개가 있고, 길이가 2인 문자열은 1개가 있다. "xyxy"의 경우에는 c("xyxy") = 2이기 때문에, 경우의 수에 포함하면 안 된다.

예제 2의 경우에는 q를 하나만 포함하고, 다른 문자를 2개 포함하는 문자열이 정답이 된다. 길이가 1인 문자열은 1개, 2인 문자열은 2*25 = 50개, 3인 문자열은 3*25^2 = 1875개가 있다.