四铺地砖

题目描述

有一条道路需要铺设地砖，这条道路由n×2个方格组成。存在两种规格的地砖，一种是1×2规格的，也就是恰好可以覆盖两个方格，另一种是2×2规格的。两种规格的砖头的数量没有限制。请计算有多少种方法，将这条道路铺满地砖。

由于方案数可能很大，输出它模1,000,000,007的余数即可。

输入描述

单个整数：表示n。

输出描述

单个整数：表示方案数模1,000,000,007的余数。

数据范围

• 对于30%的数据，1≤n≤15；
• 对于70%的数据，1≤n≤50000；
• 对于100%的数据，1≤n≤100000。