Танд тетраэдр өгөгджээ. Харгалзах оройноонуудыг $A$, $B$, $C$, $D$ гэсэн үсгүүдээр тэмдэглэв.

Шоргоолж тетраэдрын $D$ орой дээр зогсож байгаа бөгөөд тэр зүгээр сул зогсохгүй маш идэвхитэй хөдөлгөөнтэй байна. Тэр хугацааны агшин бүрт тетраэдрийн ирмэгийн дагуу нэг оройгоос нөгөө орой руу ганцхан алхаад очиж байв. Мөн тэр нэг орой дээр зогсоод байж чаддаггүй байв.

Таны даалгавар бол яг $n$ алхамаар $D$ оройгоос эхлээд буцаад өөр дээрээ ирэх хэдэн арга байгааг тоолох юм. Өөрөр хэлбэл $D$ оройгоос эхлээд өөр дээрээ ирэх $n$ урттай ялгаатай циклт замуудын тоог танаас асууж байна. Хариулт нь хэтэрхий том тоо байж болох тул та хариуг $1000000007$ ($10^{9} + 7$)-д хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.

Оролт

Нэг мөрөнд шаардсан циклт замын урт болох бүхэл тоо $n$ ($1 ≤ n ≤ 10^{7}$) байна.

Гаралт

Боломжит циклт замуудын тоог $1000000007$ ($10^{9} + 7$)-д хуваагаад гарсан үлдэгдэл байна.

Эхний жишээнд тохирох замууд:

• $D - A - D$
• $D - B - D$
• $D - C - D$