Encara més seqüències de bits P84293


Statement
 

pdf   zip

Calculeu el nombre de seqüències diferents de longitud nn, formades només per zeros i uns, i tals que no tenen més de dos uns consecutius.

Entrada

L’entrada consisteix en diversos casos, cadascun amb un natural nn entre 0 i 10910^9.

Sortida

Per a cada cas, escriviu quantes seqüències diferents de nn bits no tenen més de dos uns consecutius, mòdul 109+710^9 + 7.

Pista

Una matriu es pot elevar a un natural xx fent només Θ(log⁡x)\Theta(\log x) productes de matrius.

Public test cases

  • Input

    0
1
2
3
4
5
20
1000
123456789

    Output

    1
2
4
7
13
24
223317
475857792
357891500
    • Information
    Author
    Pol Mauri
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++