Hypercube

The N-hypercube is a directed acyclic graph with $2^N$ nodes labeled with the numbers from 0 to $2^N - 1$. There is an arc from node $x$ to node $y$ if and only if $x < y$ and there is a non-negative integer $p$ such that $x \oplus y = 2^p$, where $\oplus$ is bitwise xor.

Given three positive integers $N$, $M$, and $K$, compute the following.

1. The maximum label $i$ of a node belonging to the N-hypercube that has an arc from $i$ to $M$.
2. The minimum label $j$ of a node belonging to the N-hypercube that has an arc from $M$ to $j$.
3. The number of paths of length $K$ (paths having $K$ arcs) found in the N-hypercube. Because this number may be quite large, compute it modulo 100003.

The first line of the input contains the three numbers $N$, $M$, and $K$, each separated by one space.

The first line must contain the answer for task 1, the second line the answer for task 2, and the third line the answer for task 3.

• $2 \le K \le N \le 100{,}000$
• $1 \le M \le 100{,}000{,}000$
• For any given $M$, there is at least one arc leaving node $M$ and at least one arc reaching node $M$.
• The answer for task 3 must be computed modulo 100003.
• $\oplus$ stands for bitwise xor.