题目描述

年轻的 Bojan 现在是一名成功的电气工程专业学生，从小就喜欢涂色。想起童年时漫不经心的日子，他决定买一本涂色书和 $k$ 种颜色的颜料，然后开始工作。有趣的是，Bojan 不喜欢五颜六色的图片，所以他决定每张图片最多使用三种不同的颜色着色。此外，Bojan 永远不会用同一种颜色给两个相邻的区域上色，如果两个区域的边缘至少有一个连接点，则被视为相邻。例如，下图用 $4$ 和 $3$ 表示的区域是相邻的，而区域 $1$ 和 $2$ 则不是。此外，下面这张图片的着色方式符合 Bojan 的所有要求。

在开始给一张图片上色之前，Bojan 会问自己有多少种方法可以给这张图上色，从而满足他的所有条件。鉴于 Bojan 是学电气工程的，可以理解的是，组合学不是他的强项，所以他向你寻求帮助。

输入格式

输入仅一行两个整数 $n,k$，分别代表涂色书里面的图片编号和 Bojan 的颜料拥有的颜色数量。

涂色书将会在附件中给出（即文件 Happy coloring book.pdf），涂色书里面的图片按照先后顺序依次编号为 $1$ 到 $8$。

输出格式

输出仅一行一个整数，代表 Bojan 在满足自己所有要求的上色方式的个数。

2 2

0

5 3

12

7 3

96

提示

【数据范围】

对于所有数据，$1\leqslant n\leqslant 8$，$1\leqslant k\leqslant 1000$。

【题目来源】

本题来源自 COCI 2014-2015 CONTEST 7 T4 JANJE，按照原题数据配置，满分 $120$ 分。

由 Eason_AC 翻译整理提供。