하이퍼큐브

N-하이퍼큐브는 0부터 $2^N - 1$까지의 수가 붙은 $2^N$개의 노드로 이루어진 방향 비순환 그래프이다. 노드 $x$에서 노드 $y$로 가는 간선이 존재할 필요충분조건은 $x < y$이면서 $x \oplus y = 2^p$인 음이 아닌 정수 $p$가 존재하는 것이다. 여기서 $\oplus$는 비트 XOR 연산이다.

양의 정수 $N$, $M$, $K$가 주어졌을 때 다음 세 가지를 계산하라.

1. N-하이퍼큐브에 속한 노드 중 $i$에서 $M$으로 가는 간선이 있는 노드 $i$의 최댓값.
2. N-하이퍼큐브에 속한 노드 중 $M$에서 $j$로 가는 간선이 있는 노드 $j$의 최솟값.
3. N-하이퍼큐브에서 찾을 수 있는 길이 $K$인 경로(간선이 $K$개인 경로)의 개수. 이 수는 매우 클 수 있으므로 100003으로 나눈 나머지를 구하라.

첫째 줄에 세 수 $N$, $M$, $K$가 공백 하나를 사이에 두고 주어진다.

첫째 줄에 1번 문제의 답을, 둘째 줄에 2번 문제의 답을, 셋째 줄에 3번 문제의 답을 출력한다.

• $2 \le K \le N \le 100{,}000$
• $1 \le M \le 100{,}000{,}000$
• 주어지는 $M$에 대해 노드 $M$에서 나가는 간선과 노드 $M$으로 들어오는 간선이 각각 하나 이상 존재한다.
• 3번 문제의 답은 100003으로 나눈 나머지로 구해야 한다.
• $\oplus$는 비트 XOR 연산이다.