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

Cerința

Să se determine numărul permutărilor mulțimii {1,2,...,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 1234577.

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

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 1234577.

Restricții și precizări

• N este putere a lui 2 din mulțimea {22, 23, …, 220}
• 1 ≤ X ≤ N
• 1 ≤ K ≤ 1 + log2N
• 1234577 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).