問題文

世界最悪のバス停を投票で決めるトーナメントが開催されています。バス停は 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

入力例 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