12955번 - 팰린드롬 부분 문자열

알파벳 대문자로만 이루어진 길이가 N인 문자열 중에서, 길이가 M인 모든 부분 문자열 중에서 팰린드롬인 것의 개수가 K개 이상인 것의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 N, M, K가 주어진다. (2 ≤ M ≤ N ≤ 11, 0 ≤ K ≤ 11)

첫째 줄에 문제의 조건에 맞는 문자열의 개수를 출력한다. 정답은 2⁶³-1보다 작거나 같다.

예제 1의 경우에 길이가 2이면서, 같은 문자로 이루어진 AA, BB, CC, ..., ZZ와 같은 문자열이 정답이 된다.

예제 2의 경우에는 팰린드롬의 개수가 0이기 때문에, 길이가 2인 모든 문자열이 해당된다.