← 返回题目列表

Codeforces · 209/A

A. 五彩弹珠

中文机器翻译题面 查看原题

Polycarpus 玩红色和蓝色弹珠。他把n个弹珠从左到右排成一排。事实证明,这些弹珠形成了斑马体。

如果序列中弹珠的颜色交替,则红色和蓝色弹珠的非空序列是斑马体。例如,序列(红色;蓝色;红色)和(蓝色)是斑马纹,序列(红色;红色)不是斑马纹。

现在 Polycarpus 想知道有多少种方法可以从这个序列中挑选斑马子序列。帮他解决这个问题,求模1000000007(109+7)的数的方法。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106) — Polycarpus 序列中弹珠的数量。

输出

打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

3

输出 #1

6

输入 #2

4

输出 #2

11

注意

让我们考虑第一个测试样本。让我们假设 Polycarpus 最初有序列(红色;蓝色;红色),因此有六种方法来选择斑马:

- 拾取第一个弹珠;
- 拾取第二个弹珠;
- 拾取第三颗弹珠;
- 拾取第一个和第二个弹珠;
- 拾取第二个和第三个弹珠;
- 挑选第一、第二和第三个弹珠。

可以证明,如果Polycarpus选择(蓝;红;蓝)作为初始序列,路数不会改变。