Ели наскоро завърши гимназия и както повечето абитуриенти имаше бал. След това тя отиде на "втора бална" на морето. В нейния случай морето беше Карибско море.

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

Тя се намира в първия град на първия остров и иска да обиколи всички останали 3N – 1 града, като накрая се върне откъдето е тръгнала. Ели се чуди по колко начина може да направи това? На единствен ред на стандартния вход ще бъде зададено едно цяло число N – броят градове на всеки от трите острова. На стандартния изход изведете едно цяло число – броя възможни маршрути, които Ели може да избере. Тъй като това число може да бъде много голямо, изведете само остатъка му при деление на 1,000,003.

• 1 ≤ N ≤ 30

Примерен Вход	Примерен Изход
1	2
2	32
13	261668