SPOJ in Armenian

Թշնամիներից պաշտպանվելու համար Չինաստանի կայսրը որոշում է պարիսպ կառուցել իր կայսրության հյուսիսային սահմանին: Պարիսպի կառուցումը հանձնարարում է իր գլխավոր ճարտարապետ Ջեկի Չանին: Որպեսզի նվազեցնի ծախսված շինանյութի քանակը Ջեկին որոշում է օգտագործել միայն այս տեսքի քարեր.

##   X

#

Պարիսպի բարձրությունը ֆիքսած է 2 միավոր, բայց երկարությունը կարող է լինել տարբեր:

Ջեկիին հետաքրքրում է, թե, օգտագործելով միայն այդ երկու տեսակի քարերը, տրված երկարությամբ պարիսպը քանի հնարավոր ձևով կարելի է կառուցել:

Օրինակ 2 երկարությամբ պարիսպը կարելի է կառուցել հետևյալ 5 ձևերով.

XX

XX

##

#X

##

X#

X#

##

#X

##

Մուտքը.

Մուտքում տրված է պարիսպի N (1<=N<=100000) երկարությունը:

Ելքը

Ելքում պետք է տալ մի թիվ - պարիսպը կառուցելու բոլոր հնարավոր ձևերի քանակը 1000000007 բաժանելիս ստացված մնացորդը:

Օրինակ

Մուտքը.
7

Ելքը.
655