Background

Mirko is studying 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$

Here, $a_i$ represents a character and $s_i$ represents a string. Both consist of lowercase letters.

• $\operatorname{xor}$ denotes the bitwise XOR operator.
• $\operatorname{ord(letter)}$ denotes the position of the letter in the alphabet (for example, $\operatorname{ord(a)=1}$ and $\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 hash value $k$ and length $n$?

Input Format

One line containing three integers $n$, $k$, and $m$.

Output Format

Output one line containing the number of words of length $n$ whose hash value is $k$.

1 0 10 

0

1 2 10

1

3 16 10

4

Hint

Sample Explanation

Sample 1 Explanation

All characters in the alphabet have $\text{ord}$ values that are not $0$.

Sample 2 Explanation

The word is b.

Sample 3 Explanation

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

Constraints

$1\le n\le 10$，$0\le k<2^m$，$6\le m\le 25$。

Notes

Translated from COCI2013-2014 CONTEST #6 T5 HASH.

Translated by ChatGPT 5