Ante je kupio beskonačno domino pločica dimenzija \(2 \times 1\). Anti je obična igra domina dosadna te je smislio svoju igru. Nacrtao je pravokutnik dimenzija \(2 \times n\) te ga zanima broj načina na koji može popuniti cijeli pravokutnik. Kako broj načina može biti vrlo velik, Antu zanima samo ostatak tog broja pri dijeljenju sa \(10^9 + 7\).

Ulazni podatci

U prvom i jedinom redu nalazi se broj \(n\) \((1 \leq n \leq 10^{18})\).

Izlazni podatci

Ispišite traženi broj iz zadatka.

Podzadatci

Ulaz primjera 1

17

Izlaz primjera 1

2584

Ulaz primjera 2

5000

Izlaz primjera 2

419609281

Ulaz primjera 3

395847129854321240

Izlaz primjera 3

725934990