xnk

Se consideră numerele naturale nenule $X$, $N$, $K$, unde $N$ este o putere a lui $2$. Pentru o permutare $p = (p_1, p_2, \dots, p_N)$ a mulțimii $\{1, 2, \dots, N\}$ se determină maximul după modelul din exemplul de mai jos:

Cerința

Să se determine numărul permutărilor mulțimii $\{1, 2, \dots, N\}$ în care valoarea $X$ va fi prezentă pe nivelul $K$, nu și pe nivelul $K - 1$. Pentru că acest număr poate fi foarte mare, se va determina modulo $1 \ 234 \ 577$.

Date de intrare

Fișierul de intrare xnk.in conține pe prima linie trei numere naturale $X$, $N$ și $K$ despărțite prin spațiu.

Date de ieșire

În acest caz, fișierul de ieșire xnk.out va conține pe prima linie un singur număr natural reprezentând numărul permutărilor care îndeplinesc condițiile cerute, modulo $1 \ 234 \ 577$.

Restricții și precizări

• $N \in \{2^2, 2^3, \dots, 2^{20}\}$
• $1 \leq X \leq N$
• $1 \leq K \leq 1 + \log_{2} N$
• $1 \ 234 \ 577$ este număr prim

Exemplul 1

xnk.in

1 8 3

xnk.out

0

Explicație

Valoarea $1$ nu poate să apară pe nivelul $3$, ci numai pe nivelul $4$.

Exemplul 2

xnk.in

2 4 2

xnk.out

8

Explicație

Cele $8$ permutări sunt: $(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)$