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 programme 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. 

힌트

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”.

1 0 10

0

1 2 10

1

3 16 10

4