遮蔽苍穹

第六道门后是一片天空——不是火星的天空，是地球的天空，蓝色的，有白云。

"Echo的天气模块。"Nyx说，"她偶尔会梦见地球。梦见云、雨、风。"

"我们要做啥子？"CC问。

"预测天气。"你说，"每天有一片云会覆盖一部分天空。我们要找到连续N天，云覆盖所有需要观测的区域。"

"这就像……"CC想了想，"像拼图。每天拼一块，最后拼出整张图。"

"对。"

你开始写。4×4的天空，每天有一片云覆盖7个相连的格子（一个2×2方块加上相邻的一些格子）。每天云的位置可以不同。需要找到N天的云位置序列，使得每个需要观测的格子至少被覆盖一次。

屏幕上跳出了结果。方案数：3。

"三天。"你说，"三种不同的覆盖方式。"

"三种梦。"Echo说，"我做过三种关于地球的梦。第一种是晴天，第二种是雨天，第三种是……"

"第三种是啥子？"CC问。

"第三种。"Echo说，"是你们在。"

CC没有说话。她只是把服务器抱得更紧了一点。

天空中的云朵慢慢消散，露出第七道门——一扇由藤蔓编织的门，上面长满了紫色的乳草。

"走。"你说。

题目描述

$4\times 4$ 的区域。每天有一片云覆盖7个相连的格子（形状为一个2×2方块及其相邻格子）。给定 $N$ 天（$N ≤ 7$），求有多少种不同的云的放置序列，使得每个格子至少被覆盖一次。

输入格式

$N$。

输出格式

方案数。

输入样例

2 2
..
..

输出样例

1

提示

• DFS 枚举每天的云位置。用位掩码记录已覆盖的格子。
• 剪枝：当前已覆盖格子数加上剩余天数最多能覆盖的格子数 $< 16$ 时剪枝。
• 注意云的形状固定，需预先计算出所有合法的云位置。

第七道门后是一片菌毯。不是火星的荒漠——是一片蔓延的菌毯，绿色的，散发着一种奇怪的气味。

"毒菌。"CC说，"我小时候见过。矿区外面长满了这种菌，有毒，矿工都不碰。"

"但它会蔓延。"你说，"从一个格子开始，每周向八个方向扩散一格。我们要算它需要多少周才能占领整片草地。"

"这就像……"CC想了想，"像瘟疫。一开始只有一个人生病，然后传染给周围所有人。"

"对。"