33702번 - 비밀번호

문제

쿠는 9ドル$자리 비밀번호를 정하려고 한다. 비밀번호 버튼은 아래와 같이 생겼다.

쿠가 만들고 싶은 비밀번호의 조건은 아래와 같다.

• 가장 먼저 $K$가 적힌 버튼을 눌러야 한다.
• 이후 직전에 누른 버튼과 상하좌우로 인접한 버튼을 눌러야 한다.
• 각 버튼을 한 번씩만 눌러야 하며, 모든 버튼을 눌러야 한다.

$K$가 적힌 버튼에서 비밀번호를 누르기 시작할 때 만들 수 있는 서로 다른 비밀번호의 개수를 구해보자.

입력

쿠가 비밀번호를 가장 먼저 누르는 버튼에 적힌 수 $K$가 주어진다. $\left(1 \leq K \leq 9\right)$

출력

$K$가 적힌 버튼에서 비밀번호를 누르기 시작할 때, 만들 수 있는 서로 다른 비밀번호의 개수를 출력한다.

제한

힌트

두 버튼이 인접해 있다는 것은 두 버튼이 변을 공유한다는 것을 의미한다.