patrate

Adriana a învățat la școală probleme de umplere a unei suprafețe. Problema de astăzi constă în umplerea unui dreptunghi cu lungimea de $N$ cm și lățimea de $3$ cm cu ajutorul pătratelor care au latura de $1$ cm și a pătratelor care au latura de $2$ cm.

Adriana a reușit destul de ușor să rezolve problema, dar și-a dat seama că problema are mai multe soluții și este curioasă să afle în câte moduri distincte se poate umple dreptunghiul cu lungimea de $N$ cm și lățimea de $3$ cm, având la dispoziție pătrate cu latura de $1$ cm și pătrate cu latura de $2$ cm.

Cerință

Ajutați-o pe Adriana să determine numărul de moduri distincte de umplere a dreptunghiului din enunț. Deoarece acest număr poate fi foarte mare, este suficient să aflați restul împărțirii acestui număr la $1.000.000.007$.

Date de intrare

Fișierul de intrare patrate.in conține pe prima linie un număr natural $N$.

Date de ieșire

În fișierul de ieșire patrate.out se va scrie un singur număr natural, care reprezintă numărul de posibilități de umplere a dreptunghiului specificat în enunț, modulo $1.000.000.007$.

Restricții și precizări

• $3 \leq N \leq 1.000.000.000$;
• Pentru $30\%$ din teste, $3 \leq N \leq 15$;
• Pentru $60\%$ din teste, $3 \leq N \leq 100.000$;
• Testele nu sunt cele din timpul concursului.

Exemplul 1

patrate.in

3

patrate.out

5

Explicație

Exemplul 2

patrate.in

85

patrate.out

928344252