1921: 贴墙砖

【题目描述】

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

用这两种瓷砖贴一个2×N的墙壁，例如一个2×3的墙壁有5种方法，如下图所示。

试计算墙壁长为N时，有多少种不同的贴砖方法。

【输入格式】

输入一个整数N(1≤N≤1000000)，表示墙壁的长度。

【输出格式】

输出贴瓷砖方法总数的后4位，如果不足4位就输出整个答案。

【输入样例1】

3

【输出样例1】

5

【输入样例2】

15

【输出样例2】

5501

3

5