Problem Description

Young Bojan is now a successful electrical engineering student who has always loved coloring since childhood. Reminiscing about his carefree days, he decided to buy a coloring book and $k$ colors of paint, and then start his work. Interestingly, Bojan dislikes colorful pictures, so he decided to use no more than three different colors for each picture. Additionally, Bojan will never color two adjacent areas with the same color. If two areas share at least one common edge point, they are considered adjacent. For example, the areas labeled $4$ and $3$ in the diagram below are adjacent, while areas $1$ and $2$ are not. Furthermore, the coloring method in the picture below meets all of Bojan's requirements.

Before starting to color a picture, Bojan wonders how many ways there are to color the picture while meeting all his conditions. Given that Bojan is studying electrical engineering, it is understandable that combinatorics is not his strong suit, so he is asking for your help.

Input Format

The input consists of a single line with two integers $n$ and $k$, representing the picture number in the coloring book and the number of colors Bojan has, respectively.

The coloring book will be provided in the attachment (i.e., the file Happy coloring book.pdf), with the pictures numbered sequentially from $1$ to $8$.

Output Format

The output should be a single line containing an integer, representing the number of ways Bojan can color the picture while meeting all his requirements.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

0

Sample Input #2

5 3

Sample Output #2

12

Sample Input #3

7 3

Sample Output #3

96

Notes

[Data Range]

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

[Problem Source]

This problem is from COCI 2014-2015 CONTEST 7 T4 JANJE, configured according to the original problem data, with a full score of $120$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分