AT_relay2018_h.最悪のバス停決定戦

正在举行一场比赛，旨在通过投票选出世界上最糟糕的公交车站。参加比赛的公交车站有 $2^N$ 个。在公交车站 $i$ 和公交车站 $j$ ($i < j$) 进行对决时，除非有特殊情况，公交车站 $i$ 总是会胜出，进入下一轮。

比赛的规则如下：

• 首先，选择一个由 $2^N$ 个公交站组成的排列 $(p_1, \ldots, p_{2^N})$。
• 接着安排对决：公交站 $p_1$ 对阵 $p_2$，公交站 $p_3$ 对阵 $p_4$，依次类推，直到公交站 $p_{2^N-1}$ 对阵 $p_{2^N}$。
• 下一轮中，继续安排上一轮的每两个胜者进行对阵，比如公交站 $p_1, p_2$ 的胜者对阵 $p_3, p_4$ 的胜者，依此类推。

最终，在最后一轮中，来自前半区的胜者将与来自后半区的胜者对决。

Snuke 君支持的公交站是 $M$。在与其他公交站的对战过程中，Snuke 君可以为公交站 $M$ 做不超过 $K$ 次宣传。只要有宣传，公交站 $M$ 在那场对战中一定会胜出。

你的任务是计算出所有可能的初始排列 $(p_1, \ldots, p_{2^N})$ 中，通过 Snuke 君适当的宣传后，公交站 $M$ 能够最终获胜的排列数量，并将这个数量对 $10^9+7$ 取模。

输入包含三个整数：$N$，$M$ 和 $K$。

输出一个整数，表示通过宣传后公交站 $M$ 能够获胜的初始排列数量，对 $10^9+7$ 取模。

• $1 \le N \le 20$
• $1 \le M \le 2^N$
• $0 \le K \le 20$

示例

例如满足条件的初始排列有 $ (1,2,3,4),(1,2,4,3),(2,1,3,4),(2,1,4,3),(3,4,1,2),(3,4,2,1),(4,3,1,2),(4,3,2,1) $，总共有 $8$ 个。

本翻译由 AI 自动生成