Counting Strings

Time limit2sMemory limit512 MB

Summary

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.

Level: Hard9 of 10
Topics: Dynamic programming, String matching, Combinatorics, Matrix
Solved: No attempts yet

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 \times K$ and at most $L \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 \le L \le 100$ , $0 \le N \le 1000$ , $0 \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 \times 25 = 50$ of length 2, and $3 \times 25^2 = 1875$ of length 3.

Examples4

Example 1
Input
```
xy 2 1
```
Expected output
```
2079
```
Example 2
Input
```
q 2 1
```
Expected output
```
1926
```
Example 3
Input
```
ababab 5 4
```
Expected output
```
527166180
```
Example 4
Input
```
fgcdx 10 3
```
Expected output
```
586649223
```