Упаковочна машина

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

1. одного Діда Мороза в упаковку одного з двох видів;

2. одну Снігуроньку;

3. Діда Мороза і Снігуроньку в одну упаковку.

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

Вхідні дані

Перший рядок вхідного файлу містить ціле число n (1 ≤ n ≤ 10^6).

Вихідні дані

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

Приклади