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

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

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

2. одну Снегурочку;

3. Деда Мороза и Снегурочку в одну упаковку.

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

Входные данные

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

Выходные данные

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

Примеры