Hàm băm

View as PDF
Submit solution
All submissions
Best submissions
Time limit: 1.0s , Memory limit: 256M , Points: 25 (partial)

Bi đang nghiên cứu hàm băm mà theo đó hàm này sẽ gán một giá trị số nguyên cho một từ (word). Hàm được định nghĩa đệ quy như sau:

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

Hàm chỉ xử lý từ lấy các ký tự từ Alphabet in thường. XOR là phép xor bít (ví dụ 0110 XOR 1010 = 1100). ord(letter) trả về số thứ tự của ký tự (letter) trong bảng chữ cái (ví dụ ord('a')=1). MOD là một số nguyên có giá trị là 2^M.

Xét ví dụ với M=10, ta có:

f(a) = 1
f(aa) = 32
f(kit) = 438

Bi muốn tìm xem có bao nhiêu từ có độ dài N với giá trị băm K. Hãy lập trình giúp Bi.

Input

Dòng duy nhất chứa ba số N, K, M thỏa 1 \le N \le 10, 0 \le K \le 2^M, 6 \le M \le 25.

Output

In ra số từ cần tìm.

Samples

Sample Input 1
1 2 10
Sample Output 1
1
Sample Input 2
3 16 10
Sample Output 2
4

Note

Ở testcase thứ nhất từ cần tìm là "b".

Ở testcase số hai có 4 từ là: "dxl", "hph", "lxd" and "xpx".

REF COCI

Comments