Problem Description

Young Bojan is now a successful student majoring in electrical engineering, and he has loved coloring since he was a child. Thinking back to those carefree childhood days, he decides to buy a coloring book and paints of $k$ different colors, and then get to work. Interestingly, Bojan does not like colorful pictures, so he decides that each picture will be colored using at most three different colors. Also, Bojan will never use the same color for two adjacent regions. Two regions are considered adjacent if their borders share at least one common point. For example, in the picture below, the regions labeled $4$ and $3$ are adjacent, while regions $1$ and $2$ are not. Moreover, the coloring shown below satisfies all of Bojan's requirements.

Before he starts coloring a picture, Bojan asks himself how many ways there are to color the picture while satisfying all his conditions. Since Bojan studies electrical engineering, it is understandable that combinatorics is not his strong point, so he asks you for help.

Input Format

The input contains only one line with two integers $n, k$, representing the picture index in the coloring book and the number of colors of paint Bojan has, respectively.

The coloring book is provided as an attachment (i.e., the file Happy coloring book.pdf). The pictures in the book are numbered from $1$ to $8$ in order.

Output Format

Output only one line with one integer, representing the number of coloring ways that satisfy all of Bojan's requirements.

2 2

0

5 3

12

7 3

96

Hint

Constraints

For all testdata, $1\leqslant n\leqslant 8$，$1\leqslant k\leqslant 1000$.

Source

This problem comes from COCI 2014-2015 CONTEST 7 T4 JANJE, and follows the original testdata settings, with a full score of $120$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5