← 返回题目列表

AtCoder · relay2018_h

H. 最惨烈的公交车站之战

中文机器翻译题面 查看原题

配点 : 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