문제

Author: Anton Grbin

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 2M. 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 < 2M, 6 ≤ M ≤ 25).

출력

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

예제 입력 1

1 0 10

예제 출력 1

0

예제 입력 2

1 2 10

예제 출력 2

1

예제 입력 3

3 16 10

예제 출력 3

4