E. Тетраэдр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

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

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

Оролт

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

Гаралт

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

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2
Гаралт
3
Оролт
4
Гаралт
21

Тэмдэглэл

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

  • $D - A - D$
  • $D - B - D$
  • $D - C - D$
Сэтгэгдлүүдийг ачааллаж байна...