Even more sequences of bits P84293


Statement
 

pdf   zip

thehtml

Please compute the number of different sequences of length n, made up of only zeroes and ones, and with no more than two consecutive ones.

Input

Input consists of several cases, each with a natural number n between 0 and 109.

Output

For every case, print the number of different sequences of n bits that do not have more than two consecutive ones, modulo 109 + 7.

Hint

A matrix can be powered to a natural number x with only Θ(logx) products of matrices.

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
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++