CF209A Multicolored Marbles

Polycarpus 玩着红色和蓝色的弹珠。他从左到右依次放置了 $n$ 个弹珠。最终，这些弹珠形成了一个 “斑马形”（zebroid）。 如果一个非空的红色和蓝色弹珠的序列中颜色交替出现，那么这个序列就是一个“斑马形”。例如，序列（红，蓝，红）和（蓝）是“斑马形”，而序列（红，红）则不是。 现在 Polycarpus 想知道，从这个序列中选出一个斑马形子序列有多少种不同的方式。请你帮他解决这个问题，输出方案总数对 $1000000007$（$10^{9}+7$）取模后的结果。

第一行包含一个整数 $n$，表示 Polycarpus 的弹珠序列中的弹珠数量。$1 \leq n \leq 10^{6}$。

输出一个整数，表示方案总数对 $1000000007$ 取模后的结果。

我们考虑第一个测试样例。假设 Polycarpus 最初有序列（红，蓝，红），那么取出斑马形的方式有六种： - 只选第一个弹珠； - 只选第二个弹珠； - 只选第三个弹珠； - 只选第一个和第二个弹珠； - 只选第二个和第三个弹珠； - 选全部三个弹珠（第一个、第二个和第三个）。 可以证明，如果 Polycarpus 选择（蓝，红，蓝）作为初始序列，方案数也不会改变。 由 ChatGPT 5 翻译