小D的背包问题

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 baga.in 输出文件 baga.out

【问题描述】

放寒假了,小D终于可以回家了。一个学期之后他有太多的东西想带回家。
小D的背包可以被看作一个4行N列的矩阵,每个物品放入背包的物品恰好需要占据两个相邻的方格,任意两个物品不能占据相同的方格。为了充分的利用自己的背包,小D希望背包的所有空间都放置了物品,也就是说,背包中恰好放入了2N个物品。
现在小D想知道,不同的放置方案数有多少种。

【输入文件】

       输入文件只有一行,包含一个正整数描述N。

【输出文件】

输出一行,一个整数表示不同的方案数。因为答案可能很大,你只需要输出结果对997取模后的结果。

【样例输入】

2

【样例输出】

5

【样例说明】

       五种不同的放置方案如下:
a

【评分标准】

       本题包含10个测试点,对于每个测试点,如果你的输出和标准输出完全一样则得到该测试点的全部分数,否则得0分。

【数据规模】

       对于40%的测试数据,N ≤ 1 000
       对于70%的测试数据,N ≤ 1 000 000
       对于100%的测试数据,N ≤ 1 000 000 000