В упаковочную машину загрузили \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}.