Fișierul intrare/ieșire trickortreat.in, trickortreat.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Trick or Treat

Deoarece a adoptat cu entuziasm sărbătoarea de Halloween (și pe cele de Valentine’s Day și de 4 iulie și de Ziua Recunoștinței), Vasilică vrea să meargă și el la trick-or-treating în satul bunicilor. Satul are N case. Ca să strângă mai multe bomboane, Vasilică vrea să treacă pe la fiecare casă de două ori. Totuși, el nu poate merge consecutiv de două ori la aceeași casă, deoarece locatarii și-ar da seama și l-ar alunga. Vasilică se întreabă în câte moduri poate face cele 2N vizite.

Date de intrare

Fișierul de intrare trickortreat.in conține un singur număr întreg N, reprezentând numărul de case din sat.

Date de ieșire

În fișierul de ieșire trickortreat.out se va scrie numărul de posibilități modulo 100.003.

Restricții

  • 1 ≤ N ≤ 10.000

Exemplu

trickortreat.in trickortreat.out
2 2
3 30

Explicație

Pentru N = 2 case, vizitele pot fi făcute în ordinea [1 2 1 2] sau [2 1 2 1]. Pentru N = 3, vizitele pot fi făcute în ordinile [1 2 1 3 2 3], [1 2 3 1 2 3], [1 2 3 1 3 2] etc. (dar nu [1 2 1 3 3 1] sau [1 2 1 2 3 3]).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii