H - 最悪のバス停決定戦
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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} の勝者が対戦する。
すぬけ君は、バス停 M を応援しています。すぬけ君は、バス停 M と他のバス停との対戦のうち、最大 K 回においてバス停 M を宣伝することができます。 宣伝を行うと、その対戦においては必ずバス停 M が勝つことができます。
2^N! 個の順列 (p_1, ..., p_{2^N}) で表される初期状態のうち、 すぬけ君が適切に宣伝を行うことでバス停 M がトーナメントで最終的に残ることができるものは何通りあるかを、10^9+7 で割った余りを求めてください。
制約
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 2^N
- 0 ≤ K ≤ 20
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
すぬけ君が適切に宣伝を行うことで、バス停 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