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

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

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

• X는 알파벳 소문자로 이루어져 있어야 한다.
• X의 길이는 LK보다 크거나 같고, LK+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

xy 2 1

예제 출력 1

2079

예제 입력 2

q 2 1

예제 출력 2

1926

예제 입력 3

ababab 5 4

예제 출력 3

527166180

예제 입력 4

fgcdx 10 3

예제 출력 4

586649223

힌트

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

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