26601번 - 가장 작은 수

약수를 $2^N$개 갖는 양의 정수 중 가장 작은 수를 구하자.

첫째 줄에 정수 $N$이 주어진다. $\left(0 \leq N \leq111\,222\right)$

첫째 줄에 약수를 $2^N$개 갖는 양의 정수 중 가장 작은 수를 출력한다. 단, 수가 너무 커질 수 있으니 $2\,000\,003$으로 나눈 나머지를 출력한다.

1. 약수는 어떤 수를 나누어떨어지게 하는 수를 말한다. 예를 들어 $6$의 약수는 $1, 2, 3, 6$이다.
2. $2\,000\,003$은 소수다.