Palindromic substrings

Time limit2sMemory limit512 MB

Summary

Count length-N uppercase strings whose length-M substrings include at least K palindromes.

Level: Medium5 of 10
Topics: Brute force, String, Recursion, Bit manipulation
Solved: No attempts yet

Problem

Consider the strings of length $N$ made only of uppercase letters. Such a string has one substring of length $M$ for each starting position, $N-M+1$ in total. Write a program that counts the strings for which at least $K$ of those substrings are palindromes. Substrings with the same content but different starting positions are counted separately.

Input

The first line contains $N$ , $M$ , and $K$ , separated by spaces. ( $2 \le M \le N \le 11$ , $0 \le K \le 11$ )

Output

Print the number of strings that satisfy the condition on the first line. The answer is at most $2^{63}-1$ .

Hint

For $N=2$ , $M=2$ , $K=1$ the qualifying strings are AA, BB, CC through ZZ, the ones whose two letters match. For $K=0$ no palindrome is required, so every string of length $N$ qualifies.

Examples5

Example 1
Input
```
2 2 1
```
Expected output
```
26
```
Example 2
Input
```
2 2 0
```
Expected output
```
676
```
Example 3
Input
```
3 2 1
```
Expected output
```
1326
```
Example 4
Input
```
4 4 1
```
Expected output
```
676
```
Example 5
Input
```
7 3 3
```
Expected output
```
4310176
```