3885: 砌墙
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：17
解决：4
题目描述
wall.in/wall.out
小理痴迷于游戏成绩一落千丈，为了使小理改过自新，他父亲在暑假送他去工地体验 生活的艰辛。
小理在工地的工作是砌墙，他有一个长为 N 宽为 2 的墙壁，给他两种转头：一个长 2 宽 1，另一个是 L 型覆盖 3 个单元的转头。如下图：
小理痴迷于游戏成绩一落千丈，为了使小理改过自新，他父亲在暑假送他去工地体验 生活的艰辛。
小理在工地的工作是砌墙，他有一个长为 N 宽为 2 的墙壁，给他两种转头：一个长 2 宽 1，另一个是 L 型覆盖 3 个单元的转头。如下图：
转头可以旋转，两种转头可以无限制提供。你的任务是计算用这两种来覆盖 N*2 的墙
壁的覆盖方法。例如一个 2*3 的墙可以有 5 种覆盖方法，如下：
注意可以使用两种转头混合起来覆盖，如 2*4 的墙可以这样覆盖：
给定 N，要求计算 2*N 的墙壁的覆盖方法。由于结果很打，所以只要求出输出最后 4
位。例如 2*13 的覆盖方法为 13465，只需输出 3465 即可。如果答案少于 4 位，就直接输
出就可以，不用加 0，如 N=3 时输出 5
【数据规模与约定】
对于 100%的数据，1<=N<=1000000。
输入
一个整数 N，表示墙壁的长。
输出
输出覆盖方法的最后 4 位，如果不足 4 位就输出整个答案。
样例输入 复制
13样例输出 复制
3465提示
【数据规模与约定】
对于 100%的数据，1<=N<=1000000。