提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1079 染色方案

Accept: 44    Submit: 73
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

用N*(N+1)/2块完全一样的六边形瓷砖可以拼成一个边长为N的三角形图案(所谓边长为N,是指这个三角形的外圈每边有N块瓷砖),下图就是一个边长为3的图案。

  现在对此图案染色,图案中的每块瓷砖染成黑色或白色。边长为N的图案共有多少种本质不同的染色方案?两种染色后的图案,如果其中一种可以通过旋转(顺时针旋转120度或240度)、翻转(以从上到下的中线为对称轴左右交换)得到另外一种相同的图案,则认为它们的染色方案是本质相同的,否则认为是本质不同的。

在这个问题中,N<=20,并且保证解不超过200位。

Input

输入由多个测试例组成。每个测试例对应一行输入,含一个整数N(0<=N<21),当N=0,标志输入的结束。

Output

每个测试例对应一行的输出,含一个整数,表示本质不同的染色方案数。

Sample Input

1 2 9 0

Sample Output

2 4 5864078802944

Source

FJNU Preliminary 2005

Submit  Back  Status  Discuss