人行横道
1.0 秒 262,144.0 KB 100 分
一条有 n 条线的人行横道，这 n 条线是交错的，即一条黑线一条白线。
Noder 要过马路，他不能一步完全跨过马路，途中至少要有一次踩在一条线上。他希望自己每走一步踩过的线，也是黑白交替的（单独一条白线或黑线，也算黑白交替），问他有多少种不同的走法。
由于数量太多，只需要输出对 1e9+7 取模的结果。
输入
第一行包含一个整数n（1 ≤ n ≤ 10^6），对应人行横道的长度。
输出
输出可行的方案数对 1e9+7 取模的结果。
数据范围
对于40%的数据，1≤n≤20；
对于60%的数据，1≤n≤1000；
对于100%的数据，1≤n≤106；
输入样例
3
输出样例
6
样例解释
设 3 条线编号为 1,2,3 ，符合条件的走法包括：（以下方案中的数字表示踩到的线）
一1,2,3；二1,2；三2,3；四1；五2；六3。
