ID #123 · Colecția InfoAs · Operatori și expresii

Problema Brasoveanca

_Doi pași înainte,_ _Și doi înapoi,_ _Asta-i Brașoveanca,_ _Se joacă pe la noi!_ Brașoveanca este un dans îndrăgit de toată lumea în orașul din care își are originea. Astfel că, de zilele orașului Brașov, unul din licee organizează o sumedenie de evenimente în care să se promoveze istoricul bogat și tradițiile valoroase ale brașovenilor, iar printre acestea se află și o interpretare a dansului popular eponim. Din păcate însă, liceul este unul specializat pe materii reale, iar asta înseamnă două lucruri: în primul rând, se știe că elevii de la real nu au prieteni și în al doilea rând, aceștia vor să disece orice formă de artă (incluzând dansul) în definiții matematice plictisitoare și dezolante. Din acest motiv, Brașoveanca se joacă un pic altfel aici. Fiecare pereche de dansatori începe de pe poziția `p<sub>0</sub> = 0 m`, iar la fiecare pas, aceștia pot alege dintre a înainta cu `1` pas (`1` metru) sau cu un salt (`2` metri făcuți într-o singură mișcare) față de punctul din care se află momentan. ## Cerință Curiozitatea matematică îi intrigă pe elevii liceului. Să se determine în câte moduri pot perechile să ajungă la `n` metri față de punctul de start, considerând regulile dansului explicate mai sus. Deoarece numărul poate fi foarte mare, se cere afișarea răspunsului `modulo 666013`. ## Date de intrare Fișierul de intrare `brasoveanca.in` conține un singur număr natural, `n`. ## Date de ieșire Fișierul de ieșire `brasoveanca.out` va conține o singură valoare naturală, reprezentând numărul de moduri de a ajunge la `n` metri față de punctul de start, considerând regulile dansului Brașoveanca descrise în enunț. ## Restricții și precizări ### Subtask 1 (10 puncte) * `1 ≤ n ≤ 5` ### Subtask 2 (70 de puncte) * `6 ≤ n ≤ 1.000.000` ### Subtask 3 (20 de puncte) * `1.000.001 ≤ n ≤ 1.000.000.000`