题目背景

哈希（Hash）函数是一种对数据提取特征的工具。哈希函数被广泛地应用于密码学场景。寻找哈希函数的碰撞，是入侵安全系统的一个关键步骤，我国密码学家王小云院士因完成了国际通用Hash函数的破解工作，获得了国家自然科学奖。

题目描述

定义一个从小写英文字符串映射到自然数的哈希函数 $\text{hash}$ 如下；

• 单个字符构成的字符串，哈希值定义为该字符的序号，如$\text{hash}(a)=1$，$\text{hash}(z)=26$等；
• 设$\alpha$为一个字符，$s$ 为一个字符串，则字符串 $s\cdot \alpha$（$\cdot$ 表示字符串的拼接）的哈希值定义为

$$h(s\cdot \alpha)=\left( (h(s)\times 33)\oplus h(\alpha) \right) \bmod 2^m $$

其中 $\oplus$ 表示二进制下的异或操作。例如，当 $m=6$ 时，有

• $\text{hash}(a)=1$；
• $\text{hash}(ab)=(1\times33 \oplus 2)\mod 64 = 100001_2 \oplus 10_2=100011_2=35$；
• $\text{hash}(abd)=(35\times 33\oplus 4)\mod 64=(10010000011_2\oplus100_2)\mod 64=7$。

给定哈希函数的参数 $m$，再给定一个目标值 $t$，请计算有多少长度恰好为 $n$ 的字符串，其哈希值为目标 $t$。

输入格式

单独一行：三个整数分别表示 $m$，$t$ 以及 $n$。

输出格式

单个整数：表示有多少种长度为 $n$ 的字符串，其哈希值恰好为 $t$。

10 16 3

4

样例解释 1

分别为 dxl hph lxd xpx

10 0 2

0

样例解释 2

没有长度为2的字符串，其哈希值为0

数据范围

• 对于$30\%$的数据，$6 \leq m \leq 10$，$1 \leq n \leq 5$；
• 对于$60\%$的数据，$6 \leq m \leq 20$，$1 \leq n \leq 8$；
• 对于$100\%$的数据，$6 \leq m \leq 25$，$1 \leq n \leq 10$；
• $0 \leq t < 2^m$。