Problems
Упаковочная машина
Упаковочная машина
В упаковочную машину загрузили \textbf{n} игрушечных Дедов Морозов и \textbf{n} Снегурочек. Машина может упаковать:
\begin{enumerate}
\item одного Деда Мороза в упаковку одного из двух видов;
\item одну Снегурочку;
\item Деда Мороза и Снегурочку в одну упаковку.
\end{enumerate}
Таким образом, после того, как все игрушки будут упакованы, на выходе машины будет последовательность из упаковок \textbf{4}-х видов. Сколько таких различных последовательностей может сделать машина?
\InputFile
Первая строка входного файла содержит целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}).
\OutputFile
Выведите единственное целое число --- количество различных последовательностей упаковок по модулю \textbf{1000003}.
Input example #1
1
Output example #1
5