Hash function

Time limit3sMemory limit256 MB

Summary

Count the length-N lowercase words whose repeated multiply-by-33 xor hash modulo 2^M equals K.

Level: Medium7 of 10
Topics: Divide and conquer, Hash map, Brute force, Number theory
Solved: No attempts yet

Problem

Changyoung is writing a hash function for a systems programming assignment. The function turns a word into a number and is defined recursively.

$f(\varepsilon) = 0$
$f(w + x) = ((f(w) \times 33) \oplus \mathrm{ord}(x)) \bmod 2^M$

Here $\varepsilon$ is the empty word, $w$ is a word, and $x$ is the letter appended to it. A word consists of lowercase letters only. $\oplus$ is bitwise XOR ( $0110 \oplus 1010 = 1100$ ), and $\mathrm{ord}(x)$ gives the position of $x$ in the alphabet ( $\mathrm{ord}(a) = 1$ , $\mathrm{ord}(z) = 26$ ). $A \bmod B$ is the remainder of $A$ divided by $B$ .

With $M = 10$ the hash values come out like this.

$f(a) = 1$
$f(aa) = 32$
$f(kit) = 438$

Write a program that counts the words of length $N$ whose hash value is $K$ .

Input

The first line contains $N$ , $K$ , and $M$ , separated by spaces. ( $1 \le N \le 10$ , $0 \le K < 2^M$ , $6 \le M \le 25$ )

Output

Print the number of words of length $N$ whose hash value is $K$ .

Hint

For $N = 3$ , $K = 16$ , $M = 10$ the words that satisfy the condition are dxl, hph, lxd, xpx.

Examples3

Example 1
Input
```
1 0 10
```
Expected output
```
0
```
Example 2
Input
```
1 2 10
```
Expected output
```
1
```
Example 3
Input
```
3 16 10
```
Expected output
```
4
```