시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB31181568.182%

문제

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

입력

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

출력

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

예제 입력 1

2 2 1

예제 출력 1

26

예제 입력 2

2 2 0

예제 출력 2

676

예제 입력 3

3 2 1

예제 출력 3

1326

예제 입력 4

4 4 1

예제 출력 4

676

예제 입력 5

7 3 3

예제 출력 5

4310176

힌트

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

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

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013