Fişierul intrare/ieşire:bstrings.in, bstrings.outSursăad-hoc
AutorFlorin AvramAdăugată deavram_florinavram florin constantin avram_florin
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Binary Strings

Aceasta este o problema medie.

Asa cum bine stiti, lui Gigel ii plac sirurile de caractere. De curand a inceput sa studieze sirurile binare (siruri formate din caracterele 0 si 1). Cum el este mofturos din fire, ii plac doar sirurile formate din 0 si 1 ce nu contin doua caractere consecutive de 1.

Cerinta

Gigel se intreaba cate siruri de N caractere ce respecta moftul sau exista. Cum este baiat de treaba, pentru el este suficient sa afisati raspunsul modulo 666013.

Date de intrare

Pe prima linie a fisierului bstrings.in se va afla numarul N, reprezentand numarul de caractere al sirului.

Date de ieşire

Fisierul de iesire bstrings.out va contine un singur numar, reprezentand numarul sirurilor de N caractere ce respecta moftul lui Gigel modulo 666013.

Restricţii

  • 1 ≤ N ≤ 2 000 000 000
  • Pentru 20% din teste N ≤ 20
  • Pentru 70% din teste N ≤ 1 000 000

Exemplu

bstrings.inbstrings.out
3
5

Explicaţie

Sirurile ce respecta moftul lui Gigel sunt: 000, 001, 010, 100, 101.
Celelate siruri (011, 110, 111) NU respecta moftul lui Gigel.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?