Jan's coloring book

Jan liked coloring as a child. He is now a student of electrical engineering, and he bought a coloring book and $K$ distinct colors so he can color again.

Jan does not like busy pictures, so he colors each picture with at most three different colors. He never gives the same color to two adjacent areas. If two areas share a line, he says there is no point in drawing that line and then painting both sides the same.

Two areas are adjacent when their boundaries share at least one point. In picture 3 below, areas $4$ and $3$ are adjacent, and areas $1$ and $2$ are not.

Before he starts, Jan wants the number of valid ways to color the chosen picture. Two colorings differ when at least one area has a different color.

The eight pictures are the maps below. Each vertex is an area that must be colored. Each edge joins two areas that share a boundary point. Eyes, antennae, and gray fill are not areas and are not colored.

The first and only line contains two integers $N$ and $K$ ($1 \leq N \leq 8$, $1 \leq K \leq 1000$): the index of the picture in the book and the number of colors Jan may use.

Print one integer: the number of ways Jan can color picture $N$ using the $K$ colors, with at most three colors appearing on the picture and with adjacent areas colored differently.

Picture 1. Caterpillar. The body is a path of $20$ disks. Only consecutive disks are adjacent. The eyes and the antennae are not areas.

Picture 2. A sea cottage. The dual graph has $8$ vertices: $0$ is the wall, $1$ is the door, $2$ and $3$ are the two panes of the left window, $4$ and $5$ are the two panes of the right window, $6$ is the roof, and $7$ is the attic window. The edges are $0{-}1$, $0{-}2$, $0{-}3$, $0{-}4$, $0{-}5$, $0{-}6$, $2{-}3$, $4{-}5$, $6{-}7$.

Picture 3. A well known logo. Inner disk $1$ and inner oval $2$ do not touch each other. Both sit in white interior $3$. Outer frame $4$ touches only the white interior. The edges are $1{-}3$, $2{-}3$, $3{-}4$.

Picture 4. Frosty the Snowman. The dual graph is a tree on $14$ vertices. The spine is $0{-}1{-}2{-}5{-}9$. Vertex $2$ is also adjacent to $3$ and $4$, vertex $5$ is also adjacent to $6$, $7$, and $8$, and vertex $9$ is also adjacent to $10$, $11$, $12$, and $13$.

Picture 5. An abstract ball. Concentric rings, with a horizontal cut through the inner disk and the outer ring but not through the middle ring. Vertices: inner top $0$, inner bottom $1$, middle ring $2$, outer top $3$, outer bottom $4$. Edges: $0{-}1$, $0{-}2$, $1{-}2$, $2{-}3$, $2{-}4$, $3{-}4$.

Picture 6. Pyramid. There are $10$ rows of bricks. Row $r$ has $r$ bricks ($1 \leq r \leq 10$). Consecutive bricks in a row are adjacent. The $j$-th brick in row $r$ (from the left) rests on bricks $j$ and $j{+}1$ of row $r{+}1$, and is adjacent to both.

Picture 7. Daisy. The dual graph is the same as picture 2.

Picture 8. Trampoline. The gray disk is not an area. The white rim is a $30$-cycle: $30$ sectors around the disk, with only consecutive sectors adjacent.