가장 작은 수

시간 제한1초메모리 제한1024 MB

요약

정확히 2^N개의 약수를 가진 가장 작은 양의 정수를 구하고, 2000003으로 나눈 나머지를 출력합니다.

문제

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

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

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

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

$2\,000\,003$ 은 소수다.