В упаковочную машину загрузили n игрушечных Дедов Морозов и n Снегурочек. Машина может упаковать:
одного Деда Мороза в упаковку одного из двух видов;
одну Снегурочку;
Деда Мороза и Снегурочку в одну упаковку.
Таким образом, после того, как все игрушки будут упакованы, на выходе машины будет последовательность из упаковок 4-х видов. Сколько таких различных последовательностей может сделать машина?
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 10^6).
Выведите единственное целое число — количество различных последовательностей упаковок по модулю 1000003.