204013 - 贴瓷砖

有两种瓷砖如图4.7所示,一种瓷砖长2宽1,另一种瓷砖是3个单位的L型。

用这两种瓷砖贴一个长为N宽为2的墙壁,例如一个2×3的墙壁有5种覆盖方法,如图4.8所示。

试计算有多少种不同的覆盖方法。

输入

一个整数N(1≤N≤1 000 000),表示墙壁的长。

输出

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

样例

输入

3

输出

5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题