Problem Background

Mirko is researching a hash function.

Problem Description

This hash function is defined as follows:

• $f(\rm{NULL})=0$
• $f(a_i+s_i)=((f(s_i)\times33)\operatorname{xor}\ \operatorname{ord}(a_i))\bmod MOD$

Where $a_i$ represents a character and $s_i$ represents a string, both consisting of lowercase letters.

• $\operatorname{xor}$ denotes the bitwise XOR operator.
• $\operatorname{ord(letter)}$ represents the ordinal number of the letter (e.g., $\operatorname{ord(a)=1}$, $\operatorname{ord(z)= 26}$).

$MOD$ is an integer of the form $2^m$.

When $m=10$, some values of the hash function are:

• $f(\texttt{a})=1$
• $f(\texttt{aa})=32$
• $f(\texttt{kit})=438$

How many words have a hash value of $k$ and a length of $n$?

Input Format

The input consists of a single line containing three integers $n$, $k$, and $m$.

Output Format

Output a single line, the number of words with a hash value of $k$ and a length of $n$.

Sample Input and Output

Sample Input #1

1 0 10

Sample Output #1

0

Sample Input #2

1 2 10

Sample Output #2

1

Sample Input #3

3 16 10

Sample Output #3

4

Notes

Sample Explanation

Sample 1 Explanation

None of the characters in the alphabet have an $\text{ord}$ value of $0$.

Sample 2 Explanation

The word is b.

Sample 3 Explanation

The words are dxl, hph, lxd, and xpx.

Data Constraints

$1\le n\le 10$, $0\le k<2^m$, $6\le m\le 25$.

Note

This problem is translated from COCI2013-2014 CONTEST #6 T5 HASH.

见题面 Input 部分

见题面 Output 部分