부분 문자열

알파벳 소문자로만 이루어진 단어 $N$개와 정수 $C$, $L$이 주어진다.

길이가 $L$인 문자열 중에서 주어진 단어 $N$개 가운데 정확히 $C$개를 부분 문자열로 포함하는 것이 몇 개인지 구한다. 세는 문자열도 알파벳 소문자로만 이루어진다.

첫째 줄에 $N$, $C$, $L$이 공백으로 구분되어 주어진다. ($1 \le N \le 6$, $0 \le C \le N$, $1 \le L \le 50$)

둘째 줄부터 $N$개의 줄에 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어지고, 길이는 1 이상 50 이하이다. 같은 단어가 두 번 주어지지 않는다.

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