Hash

Ο μικρός Mirko μελετά τη συνάρτηση κατακερματισμού που συνδέει αριθμητικές τιμές με λέξεις. Η συνάρτηση ορίζεται αναδρομικά με τον ακόλουθο τρόπο:

• f (κενή λέξη) = 0
• f (λέξη + γράμμα) = ((f(λέξη) ~\ast~ 33) XOR ord(γράμμα)) % MOD

Η συνάρτηση ορίζεται για λέξεις που αποτελούνται μόνο από πεζά γράμματα του αγγλικού αλφαβήτου. Το XOR αντιπροσωπεύει τον τελεστή XOR bitwise (δηλ. ~0110\;XOR\;1010\;= \;1100~), το ord(γράμμα) σημαίνει τον τακτικό αριθμό του γράμματος στο αλφάβητο ~(ord(a) = 1, ord(z) = 26)~ και ~A~%~B~ αντιπροσωπεύει το υπόλοιπο του αριθμού ~A~ όταν εκτελείτε διαίρεση ακεραίων με τον αριθμό ~B~. Το MOD θα είναι ακέραιος αριθμός της μορφής ~2^M~.

Μερικές τιμές της συνάρτησης κατακερματισμού όταν ~M = 10~:

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

Ο Mirko θέλει να μάθει πόσες λέξεις του μήκους ~N~ υπάρχουν με την τιμή κατακερματισμού ~K~. Γράψτε ένα πρόγραμμα που θα τον βοηθήσει να υπολογίσει αυτόν τον αριθμό.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τρεις ακέραιους ~N~, ~K~ και ~M\;(1 \leq N \leq 10,\;0 \leq K < 2^M,\;6 \leq M \leq 25)~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να αποτελείται από τον απαιτούμενο αριθμό από την εργασία.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων, το ~N~ δεν θα υπερβαίνει το 5.
Επιπλέον, σε περιπτώσεις δοκιμής αξίας 60% των συνολικών πόντων, το ~M~ δεν θα υπερβαίνει τους 15.

Παραδείγματα

input

1 0 10

output

0

Επεξήγηση του 1ου παραδείγματος:

Κανένας από τους χαρακτήρες στο αλφάβητο δεν έχει τιμή ord 0.

input

1 2 10

output

1

Επεξήγηση του 2ου παραδείγματος:

Είναι η λέξη "b".

input

3 16 10

output

4

Επεξήγηση του 3ου παραδείγματος:

Αυτές είναι οι λέξεις "dxl", "hph", "lxd" και "xpx".