Пакувальна машина#2948

Умова Обговорення

Пакувальна машина

1 секунда

64 мегабайти

Легка

У пакувальній машині є $n$ іграшкових Дідів Морозів та $n$ Снігуроньок. Машина може створювати пакунки наступними способами:

Один Дід Мороз в одному з двох різних типів пакунків;
Одна Снігуронька;
Дід Мороз і Снігуронька разом в одному пакунку.

Після того, як всі іграшки будуть упаковані, машина створить послідовність пакунків $4$ різних типів. Скільки різних послідовностей пакунків може виготовити машина?

Вхідні дані

У першому рядку вхідних даних задано одне ціле число $n$ (1 \leq n \leq 10^6).

Вихідні дані

Виведіть єдине ціле число — кількість різних послідовностей пакунків, обчислену за модулем $1000003$ .

Приклади

Приклад 1

Loading

Loading

1 \leq n \leq 1 0^{6}