15936번 - Hypercube 다국어

The N-hypercube is an directed acyclical graph with 2^N nodes tagged with numbers from 0 to 2^N – 1 so that there is an arc from node x to node y if and only if x < y and a non-negative integer p exists such that x ^ y = 2^p (^ operator stands for bitwise xor) .

Given N, M and K, three positive integers, you are to compute:

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 (having K arcs) found in the N-hypercube. Because this number may be quite large, you are to compute the number modulo 100003.

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

The first line of the output must contain a single number, the answer for task a. The second line must contain a single number, the answer for task b. The third line must contain a single number, the answer for task c.

• 2 ≤ K ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000,000
• For any given number M, there is at least one arc leaving node M and one arc reaching node M.
• The answer for task c must be computed modulo 100003.
• ^ operator stands for bitwise xor.