小 Mirko 正在研究一种将单词映射为数值的哈希函数（hash function）。该函数以递归方式定义如下：

• f( empty word ) = 0
• f( word + letter ) = ( ( f( word ) * 33 ) XOR ord( letter ) ) % MOD

该函数适用于仅由英文小写字母组成的单词。XOR 表示按位异或运算符（例如 $0110 \text{ XOR } 1010 = 1100$），ord(letter) 表示字母在字母表中的序号（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 \le N \le 10$，$0 \le K < 2^M$，$6 \le M \le 25$）。

输出格式

输出的第一行也是唯一的一行，应当包含题目所求的单词数量。

子任务

在占总分 $30\%$ 的测试数据中，$N$ 不超过 $5$。

此外，在占总分 $60\%$ 的测试数据中，$M$ 不超过 $15$。

样例

输入 1

1 0 10

输出 1

0

输入 2

1 2 10

输出 2

1

输入 3

3 16 10

输出 3

4

说明

样例 1 说明：字母表中没有任何字符的 ord 值为 0。

样例 2 说明：该单词为 "b"。

样例 3 说明：这些单词为 "dxl"、"hph"、"lxd" 和 "xpx"。