H - 最悪のバス停決定戦

Time Limit: 2 sec / Memory Limit: 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_1p_{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