配点 : 100 点
問題文
正在举办一场投票选出世界上最差公交车站的比赛。巴士站是 2^N 有,巴士站 i 和巴士站 j (i < j) 比赛时, 始终在公交车站,但下述例外情况除外。 i 获得更多选票并晋级下一轮。
比赛将按如下方式进行。
- 一、长度 2^N 的排列 选择 (p_1, ..., 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 优胜者,巴士站 p_5, p_6 获胜者和巴士站 p_7, p_8 优胜者,...,巴士站 p_{2^N-3}, p_{2^N-2} 获胜者和巴士站 p_{2^N-1}, p_{2^N} 的获胜者将参加比赛。
:
- 巴士站 p_1 〜 p_{2^{N-1}} 获胜者和巴士站 p_{2^{N-1}+1} 〜 p_{2^N} 的获胜者将参加比赛。
Snuke 在公交车站 我们支持 M 。 Snuke 在公交车站 M 与其他巴士站相比,最大 K 巴士站有时 M 除以宣伝你可以。 如果你做广告,比赛中总会有一个公交车站。 M 可以获胜。
2^N! 排列 (p_1, ..., p_{2^N}) 表示的初始状态中, 通过正确推广 Snuke 巴士站 M 有多少种方法可以在锦标赛中生存? 除以10^9+7 求余数。
制約
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 2^N
- 0 ≤ K ≤ 20
入力
输入是按以下格式从标准输入给出的。
N M K
出力
通过正确推广 Snuke,巴士站 M 可以赢得比赛的初始棋子数量是 10^9+7 后的余数。
入力例 1
2 3 1
出力例 1
8
满足条件的初始状态为 (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 件。
入力例 2
20 49300 4
出力例 2
77113063