Cupa InfoAs, ediția 7 · Clasa a IX-aVectori (tablouri unidimensionale)Generări de șiruri / vectori
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 p0 = 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
Exemple
3
3
5
8
Explicația exemplelor
Pentru primul exemplu. Pentru a ajunge la n = 3 metri față de punctul de start, o pereche de dansatori poate face fie trei pași, fie un pas, urmat de un salt, fie un salt, urmat de un pas. Astfel, există 3 metode de a ajunge la 3 metri față de punctul de start.
Pentru al doilea exemplu. Codificând un pas ca fiind p și un salt ca fiind s, avem următoarele 8 modalități de a ajunge la distanța de n = 5 metri față de start: ppppp, ppps, ppsp, pspp, sppp, ssp, sps, pss.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;