Polycarpus 玩红色和蓝色弹珠。他把n个弹珠从左到右排成一排。事实证明,这些弹珠形成了斑马体。
如果序列中弹珠的颜色交替,则红色和蓝色弹珠的非空序列是斑马体。例如,序列(红色;蓝色;红色)和(蓝色)是斑马纹,序列(红色;红色)不是斑马纹。
现在 Polycarpus 想知道有多少种方法可以从这个序列中挑选斑马子序列。帮他解决这个问题,求模1000000007(109+7)的数的方法。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106) — Polycarpus 序列中弹珠的数量。
输出
打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
3
输出 #1
6
输入 #2
4
输出 #2
11
注意
让我们考虑第一个测试样本。让我们假设 Polycarpus 最初有序列(红色;蓝色;红色),因此有六种方法来选择斑马:
- 拾取第一个弹珠;
- 拾取第二个弹珠;
- 拾取第三颗弹珠;
- 拾取第一个和第二个弹珠;
- 拾取第二个和第三个弹珠;
- 挑选第一、第二和第三个弹珠。
可以证明,如果Polycarpus选择(蓝;红;蓝)作为初始序列,路数不会改变。