| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 134 | 66 | 53 | 45.690% |
알파벳 소문자로만 이루어진 단어 N개와 정수 C, L이 주어졌을 때, 단어 N개 중에서 C개만 부분문자열로 포함하는 길이가 L인 문자열의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 N, C, L이 주어진다. (1 ≤ N ≤ 6, 0 ≤ C ≤ N, 1 ≤ L ≤ 50)
둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 중복되지 않는다. 단어는 50자를 넘지 않는다.
단어 N개 중에서 C개만 부분문자열로 포함하는 길이가 L인 문자열의 개수를 1,000,000,009로 나눈 나머지를 출력한다.
4 2 3 a aa aaa aaaa
50
1 0 7 abcdefgh
31810104
1 1 7 abcdefgh
0
4 3 3 a b c d
24
4 2 3 ab bc xy yz
2