Fișierul intrare/ieșire | trickortreat.in, trickortreat.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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]).