팰린드롬 부분 문자열

길이 N의 대문자 문자열 중 길이 M인 부분 문자열 가운데 회문이 K개 이상인 문자열의 수를 센다.

보통5완전 탐색문자열재귀비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제5

문제

알파벳 대문자로만 이루어진 길이 $N$ 의 문자열을 생각하자. 이런 문자열에는 길이가 $M$ 인 부분 문자열이 시작 위치마다 하나씩, 모두 $N-M+1$ 개 있다. 이 가운데 팰린드롬인 것이 $K$ 개 이상인 문자열의 개수를 구하는 프로그램을 작성하시오. 내용이 같은 부분 문자열이 서로 다른 위치에서 시작하면 각각 따로 센다.

입력

첫째 줄에 $N$ , $M$ , $K$ 가 공백으로 구분되어 주어진다. ( $2 \le M \le N \le 11$ , $0 \le K \le 11$ )

출력

첫째 줄에 조건을 만족하는 문자열의 개수를 출력한다. 정답은 $2^{63}-1$ 보다 작거나 같다.

힌트

$N=2$ , $M=2$ , $K=1$ 이면 AA, BB, CC부터 ZZ까지 두 글자가 같은 문자열만 조건을 만족한다. $K=0$ 이면 팰린드롬이 하나도 없어도 되므로 길이가 $N$ 인 문자열 전부가 조건을 만족한다.