Substring Count

Count length-L lowercase strings that contain exactly C of N given words (N at most 6, L at most 50) as substrings, modulo 1,000,000,009.

Hard8Dynamic programmingString matchingTrieCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

Problem

You are given $N$ words made of lowercase letters and two integers $C$ and $L$ .

Count the strings of length $L$ that contain exactly $C$ of the $N$ given words as a substring. The strings you count are also made of lowercase letters only.

Input

The first line contains $N$ , $C$ , and $L$ , separated by spaces. ( $1 \le N \le 6$ , $0 \le C \le N$ , $1 \le L \le 50$ )

Each of the next $N$ lines contains one word. Every word is made of lowercase letters and has length between 1 and 50. No word is given twice.

Output

Print the number of such strings modulo 1,000,000,009 on the first line.