Menara Hanoi

Apakah anda tahu tentang Menara Hanoi? Menara Hanoi merupakan permainan dengan 3 tiang dan N cakram, yang ukurannya berbeda-beda semua. Awalnya, semua cakram berada pada salah satu tiang, dan terurut, dengan cakram terbesar berada di paling bawah dan cakram terkecil berada di paling atas. Sebut saja tiang ini tiang A, dan dua tiang lainnya tiang B dan tiang C. Tujuan permainan ini adalah memindahkan N cakram tersebut ke tiang C dengan aturan berikut:

• Pada satu waktu, hanya satu cakram yang boleh dipindahkan.

• Cakram yang boleh dipindahkan merupakan cakram yang berada di posisi paling atas salah satu tiang. Cakram akan dipindahkan ke posisi paling atas salah satu tiang yang lain.

• Pada saat memindahkan, cakram yang dipindahkan tidak boleh lebih besar dari cakram teratas tiang tujuan.

Tentunya, pada akhirnya cakram-cakram itu akan terurut seperti semula, hanya saja berada pada tiang C. Diberikan N, banyak cakram, anda harus mengeluarkan solusi pemindahan cakram-cakram tersebut yang membutuhkan langkah paling sedikit.

Format Masukan

Satu baris berisi sebuah bilangan bulat N, banyaknya cakram. Cakram-cakram tersebut memiliki ukuran 1 sampai N.

Format Keluaran

Satu baris berisi sebuah bilangan bulat M, jumlah perpindahan cakram yang dilakukan dalam permainan Menara Hanoi.

Batasan

• 1 ≤ N ≤ 10

Contoh Masukan 1

3

Contoh Keluaran 1

7

Contoh Masukan 2

5

Contoh Keluaran 2

31