얀의 색칠북

얀은 어릴 적부터 색칠을 좋아했다. 지금은 전기공학을 공부하는 학생이지만, 색칠북과 서로 다른 색 $K$가지를 사서 다시 색칠을 시작했다.

얀은 알록달록한 그림을 좋아하지 않는다. 그래서 각 그림은 서로 다른 색을 최대 세 가지만 써서 칠한다. 맞닿은 두 영역은 같은 색으로 칠하지 않는다. 사이에 선이 있는데 같은 색을 쓰면 선이 아깝다는 것이 얀의 이유이다.

두 영역은 경계가 한 점이라도 공유하면 맞닿은 것으로 본다. 예를 들어 아래 설명의 그림 3에서 영역 $4$와 영역 $3$은 맞닿고, 영역 $1$과 영역 $2$는 맞닿지 않는다.

그림을 칠하기 전에 얀은 이 조건을 지키면서 그 그림을 칠하는 방법이 몇 가지인지 알고 싶어 한다. 두 색칠은 적어도 한 영역의 색이 다르면 다른 색칠이다. 얀은 조합을 잘 못 하니 여러분이 대신 세어 주면 된다.

여덟 그림의 영역은 아래 그래프와 같다. 꼭짓점은 칠할 영역이고, 변은 맞닿은 두 영역을 뜻한다. 눈, 더듬이, 회색 부분은 꼭짓점이 아니므로 칠하지 않는다.

첫째 줄에 그림 번호 $N$과 쓸 수 있는 색의 가짓수 $K$가 주어진다. ($1 \leq N \leq 8$, $1 \leq K \leq 1000$)

$N$은 색칠북에서 몇 번째 그림인지를 나타낸다.

얀이 $K$가지 색을 가지고 $N$번 그림을 칠하는 방법의 수를 한 줄에 출력한다.

그림 1. 애벌레. 몸통은 원 $20$개가 한 줄로 이어진 경로이다. 이웃한 원만 맞닿는다. 눈과 더듬이는 영역이 아니다.

그림 2. 바닷가 오두막. 영역 $8$개의 이원 그래프는 다음과 같다. 꼭짓점 $0$은 벽, $1$은 문, $2$와 $3$은 왼쪽 창의 두 칸, $4$와 $5$는 오른쪽 창의 두 칸, $6$은 지붕, $7$은 다락 창이다. 변은 $0{-}1$, $0{-}2$, $0{-}3$, $0{-}4$, $0{-}5$, $0{-}6$, $2{-}3$, $4{-}5$, $6{-}7$이다.

그림 3. 잘 알려진 로고. 안쪽 원(영역 $1$)과 그 아래 타원(영역 $2$)은 서로 떨어져 있고, 둘 다 흰 내부(영역 $3$)에 둘러싸여 있으며, 바깥 테두리(영역 $4$)는 흰 내부와만 맞닿는다. 변은 $1{-}3$, $2{-}3$, $3{-}4$이다.

그림 4. 눈사람. $14$개 영역의 이원 그래프는 나무이다. 등뼈 $0{-}1{-}2{-}5{-}9$에 잎이 붙어 있다. $2$는 $3$, $4$와도 맞닿고, $5$는 $6$, $7$, $8$과도 맞닿고, $9$는 $10$, $11$, $12$, $13$과도 맞닿는다.

그림 5. 추상적인 공. 동심원이 가로선으로 나뉜다. 안쪽 위 $0$, 안쪽 아래 $1$, 가운데 고리 $2$, 바깥 위 $3$, 바깥 아래 $4$이다. 변은 $0{-}1$, $0{-}2$, $1{-}2$, $2{-}3$, $2{-}4$, $3{-}4$이다. 가운데 고리는 가로선이 끊겨 한 영역이다.

그림 6. 피라미드. 벽돌이 $10$단이다. $r$단에는 벽돌이 $r$개 있고 ($1 \leq r \leq 10$), 같은 단에서 이웃한 벽돌은 맞닿는다. $r$단의 왼쪽에서 $j$번째 벽돌은 $r{+}1$단의 $j$번째와 $j{+}1$번째 벽돌 위에 얹혀 둘 다와 맞닿는다.

그림 7. 데이지. 이원 그래프는 그림 2와 같다.

그림 8. 트램폴린. 회색 원판은 영역이 아니다. 흰 테두리는 $30$개 조각이 원을 이루고, 이웃한 조각만 맞닿는다.