CSES - Shakkilauta
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Uolevi on $8 \times 8$ -shakkilaudan vasemmassa ylänurkassa ja haluaa päästä oikeaan alanurkkaan. Hän voi liikkua joka siirrolla askeleen vasemmalle, oikealle, ylöspäin tai alaspäin. Lisäksi hän haluaa tehdä yhteensä tasan $n$ siirtoa.

Tehtäväsi on laskea, montako mahdollista reittiä Uolevilla on. Reitin aikana saa mennä monta kertaa samaan ruutuun, mutta reitti ei saa missään kohtaa poistua shakkilaudalta.

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Ohjelmasi tulee tulostaa mahdollisten reittien määrä modulo $10^9+7$.

Rajat
  • $1 \le n \le 10^{18}$
Esimerkki

Syöte:
14

Tuloste:
3432