3271: 覆盖墙壁

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:6 解决:6

题目描述

你有一个长为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.  

输入

一个整数N(1<=n<=1000000),表示墙壁的长。

输出

输出覆盖方法的最后4位,如果不足4位就输出整个答案。

样例输入 复制

13

样例输出 复制

3465