Walking to Sincheon Station, Sam (Small)

Interview

Time limit2sMemory limit256 MB

Summary

Count N-digit numbers using only digits 0, 1, 2 that are divisible by 3 and have no leading zero.

Level: Easy3 of 10
Topics: Math, Brute force, Combinatorics
Solved: No attempts yet

Problem

Wookje loves the syllable sam, which is how Koreans read the number 3. He collects it wherever he finds it: insam (ginseng), hongsam (red ginseng), haesam (sea cucumber), Samsung, Lee Chunsam (李春森), Samsigi, samsisekki (three meals a day), nope-not-buying-that sam, sam and death, got-it sam, even Geumgangsam needs a meal first, walking to Sincheon Station sam, and above all il-i-sam (one two three). He ends half his sentences with sam too. So Wookje decided to play with the number 3.

Using only the digits 0, 1 and 2, build an $N$ digit multiple of 3. The number you build is a natural number, so it cannot start with 0. Count how many such numbers exist.

Input

The first line contains $N$ . ( $1 \le N \le 9$ )

Output

On the first line, print how many $N$ digit multiples of 3 can be written with the digits 0, 1 and 2 only.

Examples2

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
3
```
Expected output
```
6
```