해시 함수

창영이는 시스템 프로그래밍 숙제에 쓸 해시 함수를 만들고 있다. 이 함수는 단어를 숫자로 바꾸며, 다음과 같이 재귀적으로 정의된다.

• $f(\varepsilon) = 0$
• $f(w + x) = ((f(w) \times 33) \oplus \mathrm{ord}(x)) \bmod 2^M$

$\varepsilon$은 빈 단어, $w$는 단어, $x$는 그 뒤에 붙이는 한 글자다. 단어는 알파벳 소문자로만 이루어진다. $\oplus$는 비트 단위 XOR 연산이고 ($0110 \oplus 1010 = 1100$), $\mathrm{ord}(x)$는 $x$가 알파벳에서 몇 번째 글자인지를 나타낸다 ($\mathrm{ord}(a) = 1$, $\mathrm{ord}(z) = 26$). $A \bmod B$는 $A$를 $B$로 나눈 나머지다.

$M = 10$이면 해시값은 다음과 같다.

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

길이가 $N$인 단어 중 해시값이 $K$인 것이 몇 개인지 세는 프로그램을 작성하시오.

첫째 줄에 $N$, $K$, $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 10$, $0 \le K < 2^M$, $6 \le M \le 25$)

길이가 $N$이고 해시값이 $K$인 단어의 개수를 출력한다.

$N = 3$, $K = 16$, $M = 10$일 때 조건을 만족하는 단어는 dxl, hph, lxd, xpx이다.