Cerința

Un șir de biți se numește alternant dacă nu conține doi biți de 1 consecutivi. De exemplu, șirul 001001 este alternant, iar șirul 001101 nu este alternant. Să se determine numărul de șiruri de biți de lungime n care au proprietatea că sunt alternante.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul c, reprezentând numărul de șiruri de biți de lungime n care au proprietatea că sunt alternante.

Restricții și precizări

• 1 ≤ n ≤ 90

Exemplu:

Intrare

4

Ieșire

8

Explicație:

Șirurile formate din 4 biți care au proprietatea că sunt alternante sunt: 0000, 0001, 0010, 0100, 0101, 1000, 1001 și 1010.