Towers of Hanoi#5326

Towers of Hanoi

1 second

128 megabytes

Very easy

Three pegs are given. The first peg contains $n$ disks in ascending order of their size from top to bottom. The other two pegs are empty. You must move all disks from the first peg to the second. You can move each time only one disk. It is not allowed to put a larger disk on a smaller one.

How many legal configurations of $n$ disks on three pegs are there?

Input

One integer $n$ ( $1$ ≤ $n$ ≤ $20$ ).

Output

Print the number of legal configurations.

Examples

Example 1

Loading