Caribbean
МейКамп Състезание на Александър Георгиев
Time Limit: 0.1s, Memory Limit: 64MiB
Ели наскоро завърши гимназия и както повечето абитуриенти имаше бал. След това тя отиде на "втора бална" на морето. В нейния случай морето беше Карибско море.

В околността има три острова и всеки от тях има по N града, разположени по крайбрежието. Островите са населени с канибали, затова пътуването по суша между градовете е много опасно. За сметка на това пътуването с лодка е сравнително сигурно и разпространено (pirates of the Caribbean are overrated). Единственият проблем е, че лодкарите, подобно на шофьорите на такси в Студентски Град, не са вчерашни и не взимат пътници на къси разстояния (тоест между два града на един и същ остров). Така единствените възможности на Ели за пътуване е между градове на различни острови.

Тя се намира в първия град на първия остров и иска да обиколи всички останали 3N – 1 града, като накрая се върне откъдето е тръгнала. Ели се чуди по колко начина може да направи това?
Вход
На единствен ред на стандартния вход ще бъде зададено едно цяло число N – броят градове на всеки от трите острова.
Изход
На стандартния изход изведете едно цяло число – броя възможни маршрути, които Ели може да избере. Тъй като това число може да бъде много голямо, изведете само остатъка му при деление на 1,000,003.
Ограничения
  • 1 ≤ N ≤ 30
Примерен Вход Примерен Изход
12
232
13261668
В първия пример възможните пътища са 1-2-3-1 и 1-3-2-1. Един от 32-та възможни пътя във втория пример е 1-3-5-2-6-4-1 (градове 1 и 2 са на първия остров, 3 и 4 са на втория и 5 и 6 са на третия). В третия пример не забравяйте да изведете отговора по модул 1000003.
Мрън!