걷다보니 신천역 삼 (Small)

면접 대비

시간 제한2초메모리 제한256 MB

요약

0, 1, 2만 사용해 만든 N자리 수 중 3의 배수이면서 0으로 시작하지 않는 수의 개수를 센다.

난이도: 쉬움10점 중 3점
유형: 수학, 완전 탐색, 조합론
정답자: 아직 제출이 없습니다

문제

욱제는 '삼'이라는 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그중에서도 일이삼을 가장 좋아한다. 그래서 욱제는 숫자 3을 가지고 놀아보기로 했삼.

숫자 0, 1, 2만 써서 $N$ 자리 3의 배수를 만들어 보삼. 만드는 수는 자연수라서 맨 앞자리가 0인 수는 만들 수 없삼. 이런 수가 모두 몇 개나 나오는지 세어 보삼.

입력

첫째 줄에 $N$ 을 입력받으삼. ( $1 \le N \le 9$ )

출력

0, 1, 2만 써서 만들 수 있는 $N$ 자리 3의 배수의 개수를 첫째 줄에 출력하삼.

예제2

예제 1
입력
```
1
```
예상 출력
```
0
```
예제 2
입력
```
3
```
예상 출력
```
6
```