cho.sh

Counting Strings

Count strings over the lowercase alphabet whose length lies between L*K and L*K+N and in which at most K non-overlapping copies of a given pattern S can be found.

Hard9Dynamic programmingString matchingCombinatoricsMatrixNo attempts yetTime limit2sMemory limit512 MB

Problem

A string S of length L is given. For any string T, define c(T) as the largest number of occurrences of S inside T that do not overlap each other. The characters of S have to appear consecutively inside T.

For example, if S = "ab", then c("xyz") = 0 and c("ababxab") = 3. If S = "aaa", then c("aa") = 0 and c("aaaaaa") = 2.

Given two integers N and K, write a program that counts the strings X satisfying all three conditions below.

  • X consists of lowercase letters only.
  • The length of X is at least L×KL \times K and at most L×K+NL \times K + N.
  • c(X) = K.

When K = 0, a string X of length 0 also satisfies the conditions. The empty string has c value 0, so it is included in the count.

Input

The first line contains the string S and the integers N and K, separated by spaces.

S consists of lowercase letters only and its length is L. (1≤L≤1001 \le L \le 100, 0≤N≤10000 \le N \le 1000, 0≤K≤1090 \le K \le 10^9)

Output

Print the number of strings X that satisfy the conditions, modulo 1,000,000,009, on the first line.

Hint

Take S = "xy", N = 2, K = 1. There are 2027 strings of length 4 that contain "xy" at least once. Among them "xyxy" has c value 2, so it is dropped and 2026 remain. There are 52 strings of length 3 and 1 string of length 2, so the answer is 2079.

Take S = "q", N = 2, K = 1. The strings that count are the ones holding exactly one q. There is 1 such string of length 1, 2×25=502 \times 25 = 50 of length 2, and 3×252=18753 \times 25^2 = 1875 of length 3.