ACM谜题

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file acmpuzzle.in Output file acmpuzzle.out

【题目描述】

儿童机协会(Association of Children Machines,ACM)正计划给小朋友们设计一类新的拼图游戏。这些拼图都是3*N的网格,并且使用如下的图形进行拼接。这些图形都可以出现任意次。由于ACM推出的这种拼图供不应求,因此许多别的公司发布了外观相同的仿制品,例如“穿越拼图”,“拼图联盟”。

为了阻止假冒产品,ACM已经采取了措施,他们希望借此帮助商家避免自己的商店中出现仿品。因为所有的拼图都是3*N的网格,并且对于较大的N,一个3*N的拼图可能有无数种放法。ACM的工厂制作的所有拼图都只会有几种特定的放法数量。这个数量是独一无二的,并且只是所有N对应放法数的一小部分。因此假冒产品的放法数很可能不同。你将在最初的部分帮助他们:给出N的值,你将要找出用给定图形填满3*N拼图的方案总数。这些图形不能旋转,但每个图形都可以用任意多次。当然,有的图形仅仅是另外图形旋转得到的,但它们同样不能被旋转。例如,倒着的T型(棕色块)不能被旋转成正着的T型(粉色块)。

【输入格式】

输入文件包含多组数据。

每组数据有1行,包含一个正整数N(0<N<2001)。N表示网格的宽度。网格的高度总是3.

输入结束标志为N=0.不必处理这组数据。

【输出格式】

对每组数据,输出一行。这一行是一个固定的串,后面跟上方案数模10^12的值。具体格式见样例。

【样例输入】


5

100

0


【样例输出】


Case 1: 26

Case 2: 584039302899


【样例解释】

N=5的情况

【来源】

Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman

UVa12117 ACM Puzzles