P7794 [COCI 2014/2015 #7] JANJE

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.

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 only one line with one integer, representing the number of coloring ways that satisfy all of Bojan's requirements.

**Constraints** For all testdata, $1\leqslant n\leqslant 8$，$1\leqslant k\leqslant 1000$. **Source** This problem comes from **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T4 JANJE_**, and follows the original testdata settings, with a full score of $120$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5