2113. Hash

Little Mirko is studying the hash function which associates numerical values to words. The function is defined recursively in the following way:

   f( empty word ) = 0

   f( word + letter ) = ( ( f( word ) * 33 ) XOR ord( letter ) ) % MOD

The function is defined for words that consist of only lowercase letters of the English alphabet. XOR stands for the bitwise XOR operator (i.e. 0110 XOR 1010 = 1100), ord(letter) stands for the ordinal number of the letter in the alphabet (ord(a) = 1, ord(z) = 26) and A % B stands for the remainder of the number A when performing integer division with the number B. MOD will be an integer of the form `2^M`.

Some values of the hash function when M = 10:

   f( a ) = 1

   f ( aa ) = 32

   f ( kit ) = 438

Mirko wants to find out how many words of the length `N` there are with the hash value `K`. Write a program to help him calculate this number.

The first line of input contains three integers `N`, `K` and `M` (`1\ ≤\ N\ ≤\ 10`, `0\ ≤\ K\ <\ 2^M` , `6\ ≤\ M\ ≤\ 25`).

The first and only line of output must consist of the required number from the task.

1 0 10

0

1 2 10

1

3 16 10

4

Clarification of the first example: None of the characters in the alphabet has an ord value 0.

Clarification of the second example: It is the word “b”.

Clarification of the third example: Those are the words “dxl”, “hph”, “lxd” and “xpx”.