Problem Description

A tournament is being held to vote for the worst bus stop in the world. There are $2^N$ bus stops, and when bus stop $i$ competes against bus stop $j$ ($i < j$), bus stop $i$ will always receive more votes and advance to the next round, except for certain exceptions which will be described later.

The tournament proceeds as follows:

• First, choose a permutation of length $2^N$, denoted as $(p_1, ..., p_{2^N})$.
• Bus stops $p_1$ and $p_2$, $p_3$ and $p_4$, ..., $p_{2^N-1}$ and $p_{2^N}$ compete against each other.
• The winners of bus stops $p_1, p_2$ and $p_3, p_4$, the winners of bus stops $p_5, p_6$ and $p_7, p_8$, ..., the winners of bus stops $p_{2^N-3}, p_{2^N-2}$ and $p_{2^N-1}, p_{2^N}$ compete against each other.

:

• The winners of bus stops $p_1$ to $p_{2^{N-1}}$ and the winners of bus stops $p_{2^{N-1}+1}$ to $p_{2^N}$ compete against each other.

Snuke is rooting for bus stop $M$. Snuke can advertise for bus stop $M$ up to $K$ times in its matches against other bus stops. When advertising is done, bus stop $M$ is guaranteed to win that match.

Among the $2^N!$ permutations $(p_1, ..., p_{2^N})$ representing initial states, how many can Snuke ensure bus stop $M$ wins the tournament by appropriately advertising, modulo $10^9+7$?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $

Output Format

Output the number of initial states where Snuke can ensure bus stop $M$ wins the tournament by appropriately advertising, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2 3 1

Sample Output #1

8

Sample Input #2

20 49300 4

Sample Output #2

77113063

Notes/Hints

Constraints

• $1 \leq N \leq 20$
• $1 \leq M \leq 2^N$
• $0 \leq K \leq 20$

Sample Explanation 1

The initial states that satisfy the conditions are $(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)$, totaling 8.

见题面 Input 部分

见题面 Output 部分