OI题库

【问题描述】

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

【输入文件】

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

【输出文件】

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

【样例输入】

2

【样例输出】

5

【样例说明】

       五种不同的放置方案如下：

【评分标准】

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

【数据规模】

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