← 返回题目列表

Codeforces · 336/E

E. 瓦西里熊和绘画广场

中文机器翻译题面 查看原题

瓦西里熊有两个最喜欢的整数 n 和 k 以及一支铅笔。此外,他还有装有不同水彩颜料的 k 罐子。所有罐子都以某种方式从 1 到 k(含)进行编号。第 i 号罐子包含第 i 种颜色的油漆。

最初,熊拿起一支铅笔,在坐标平面上画了四段。它们都在点 (0, 0) 结束。它们从以下位置开始:(0, 2n)、(0, - 2n)、(2n, 0)、( - 2n, 0)。然后,对于每个 i = 1, 2, ..., n,熊画了两个正方形。第一个正方形具有以下顶点坐标:(2i, 0)、( - 2i, 0)、(0, - 2i)、(0, 2i)。第二个正方形具有以下顶点坐标:( - 2i - 1, - 2i - 1), ( - 2i - 1, 2i - 1), (2i - 1, - 2i - 1), (2i - 1, 2i - 1)。之后,小熊又画了一个正方形:(1, 0)、(- 1, 0)、(0, - 1)、(0, 1)。上述所有点构成点集A。

n = 0时最终图片的样本

n = 2时最终图片的样本

熊决定用 k 步画出结果图。第 i 个动作由以下阶段组成:

1. 熊在集合 А 中选择 3 个不同的点,以便任何一对选定的点之间在图片上都有一个线段。所选点和线段标记不得包含任何先前绘制的点的区域。
2. 熊绘制由所选点包围的区域并分割第 i 种颜色。

请注意,在第 k 次移动之后,图片的某些部分可能保持未绘制状态。

熊让你计算一下,有多少种不同的方式来画他的画。绘制图片的一种方法是他在每一步中选择的三元素点集序列。如果存在这样的数字 i (1 ≤ i ≤ k),并且这些序列的第 i 个成员作为集合不一致,则认为两个序列是不同的。由于要查找的数字可能很大,因此只需计算除以数字 1000000007 (109 + 7) 后的余数即可。

输入

第一行包含两个整数 n 和 k,用空格分隔(0 ≤ n,k ≤ 200)。

输出

精确打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

0 0

输出 #1

1

输入 #2

0 1

输出 #2

8

输入 #3

0 2

输出 #3

32

输入#4

1 1

输出#4

32