Tower of Hanoi бодлогын дагуу: n ширхэг, хэмжээгээрээ ялгаатай диск болон 3 гадас өгөгдөнө. Эхэндээ бүх диск нь нэгдүгээр гадас дээр, томоосоо доош дараалсан байршилтай байна.

Дискүүдийг нэгдүгээр гадаснаас гуравдугаар гадас руу зөөх шаардлагатай.

Зөөхдөө дараах дүрмийг баримтална:

• Нэг үйлдлээр зөвхөн нэг диск зөөж болно.
• Ямар ч үед жижиг диск дээр том диск тавьж болохгүй.

Бүх дискийг гуравдугаар гадас руу зөөхөд шаардлагатай хамгийн бага үйлдлийн тоо-г \(10^9+7\) тоонд хуваахад гарах үлдэгдлийг олно.

Оролт:

n бүхэл тоо өгөгдөнө.

Гаралт:

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

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

• \(1 \leq n \leq 10^{18}\)

Дэд бодлого

Жишээ:

Оролт-1

3

Гаралт-1

7