Таны даалгавар бол 2x1 эсвэл Г хэлбэрийн 3 блокоос бүрдсэн хавтангаар 2xn хүснэгтийг бүрэх бүх боломжийг тоолох явдал юм. Г хэлбэрийн болон 2x1 хэмжээт хавтангуудыг \(90^o, 180^o, 270^o\) -аар эргүүлж болно. Жишээ нь:

Оролт:

Оролтын файлын эхний мөрөнд n гэсэн бүхэл тоо өгөгдөнө.

Гаралт:

Нийт боломжийн тоог \(10^9+7\) тоонд хуваагаад гарсан үлдэгдэл болох нэг тоог хэвлэнэ.

Хязгаарлалтууд:

• Оролтын бүх утгууд нь бүхэл тоо байна.
• \(1 \leq N \leq 10^5\)

Дэд бодлого

Жишээ:

Оролт-1

2

Гаралт-1

2

Оролт-2

3

Гаралт-2

5