Counting Words with a Given Hash Value

You are given a hash function defined recursively as follows:

$$f(\mathtt{NULL}) = 0,$$ $$f(a_i+s_i) = \Bigl(\bigl(f(s_i)\times 33\bigr) \oplus \operatorname{ord}(a_i)\Bigr)\bmod 2^m, $$

where each letter (a_i) and string (s_i) consist of lowercase letters. Here, (\oplus) denotes the bitwise XOR operator and (\operatorname{ord}(letter)) returns the alphabetical rank of the letter (i.e. (\operatorname{ord}(a)=1, \ operatorname{ord}(b)=2, \dots, \operatorname{ord}(z)=26)).

For example, when (m=10) (thus (MOD=2^{10}=1024)) the following hold:

• \(f(\mathtt{a}) = 1\)
• \(f(\mathtt{aa}) = 32\)
• \(f(\mathtt{kit}) = 438\)

Your task is: given three integers \(n\), \(m\) and \(k\), count the number of words (i.e. strings of lowercase letters) of length \(n\) whose hash value is exactly \(k\) when computed using the hash function above. Since the answer can be huge, output it modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three integers:

• \(n\) \( (1 \leq n \leq 10^5)\): length of the word.
• \(m\) \( (1 \leq m \leq 10)\): exponent such that \(MOD=2^m\).
• \(k\) \( (0 \leq k < 2^m)\): the desired hash value.

outputFormat

Output a single integer: the number of words of length \(n\) whose hash value equals \(k\), modulo \(10^9+7\).

sample

1 10 1

1