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