Fişierul intrare/ieşire:trickortreat.in, trickortreat.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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.intrickortreat.out
22
330

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 sa te autentifici pentru a trimite solutii. Click aici