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 10^{9}.

**Output**

For every case, print the number of different sequences of *n* bits
that do not have more than two consecutive ones,
modulo 10^{9} + 7.

**Hint**

A matrix can be powered to a natural number *x*
with only Θ(log*x*) 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++
- Event
- Vuitè Concurs de Programació de la FME
- Date
- 2011-12-21