204013 - 贴瓷砖

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

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

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

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

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