时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一个 \(2\) 米宽 \(N\) 米长走廊，砖匠师傅打算用下面两种形状的地砖来铺满，那么可能有多少种不同的铺法？

【输入格式】

　　一个整数 \(N\)，表示走廊的长度。　　

【输出格式】

　　输出铺设方法数的最后五位数字，如果不足五位，就直接输出。

【输入输出样例1】

　Input

3

　Output

5

【样例1说明】

　　五种铺设方法如下：

【输入输出样例2】

　Input

20

　Output

18626

【数据限制】

　　对于 \(100\%\) 的数据满足，\(1≤N≤5000000\)。

【来源】

　　Mr.he