贴瓷砖

成绩 100 开启时间 2020年02月19日 星期三 14:20
折扣 0.8 折扣时间 2020年02月19日 星期三 14:20
允许迟交 是 关闭时间 2020年02月19日 星期三 14:20
输入文件 tile.in 输出文件 tile.out

【题目描述】贴瓷砖（tile）

用两种瓷砖贴一个长为N宽为2的墙壁：一种瓷砖长2宽1，另一种瓷砖是三个单位的L型，如图4.8所示。

图4.8

 

例如一个2×3的墙壁有5种覆盖方法，如图4.9所示。

图4.9

 

试计算覆盖方法数。

【输入格式】

一个整数N（1≤N≤1 000 000），表示墙壁的长。

【输出格式】

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

【输入样例1】

3

【输出样例1】

5

【输入样例2】

15

【输出样例2】

5501