| Fişierul intrare/ieşire: | bstrings.in, bstrings.out | Sursă | ad-hoc |
| Autor | Florin Avram | Adăugată de |  avram florin constantin •avram_florin |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | bstrings.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.
