小红的小球染色期望
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题与《B.小红的小球染色》共享题目背景，但是所求内容与范围均不同，我们建议您重新阅读题面。
\hspace{15pt}有 n 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数的期望。

输入描述:

\hspace{15pt}在一行上输入一个正整数 n \left(1 \leqq n \leqq 10^6\right) 代表小球数量。

输出描述:

\hspace{15pt}可以证明答案可以表示为一个不可约分数 \tfrac{p}{q} ，为了避免精度问题，请直接输出整数 \left(p \times q^{-1} \bmod M\right) 作为答案，其中 M = 10^9+7 ，q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。
\hspace{15pt}更具体地，你需要找到一个整数 x \in [0, 10^9+6] 满足 x \times q 对 10^9+7 取模等于 p，您可以查看第二个样例解释得到更具体的说明。
示例1

输入

复制 
3

输出

复制 
1

说明

\hspace{15pt}在这个样例中，第一次选取，一共有两种不同的选取情况： 
\hspace{23pt}\bullet\,选中第一、二个球； 
\hspace{23pt}\bullet\,选中第二、三个球。 
\hspace{15pt}不管是哪一种选法，染完颜色后均无法继续操作。所以，期望操作次数为 1 次。
示例2

输入

复制 
4

输出

复制 
666666673

说明

\hspace{15pt}在这个样例中，第一次选取，一共有三种不同的选取情况： 
\hspace{23pt}\bullet\,选中第一、二个球； 
\hspace{23pt}\bullet\,选中第二、三个球； 
\hspace{23pt}\bullet\,选中第三、四个球。 
\hspace{15pt}其中，第二种选取方式染色后无法继续操作；而第一、三种选取方式染色后还可以进行一次染色。 
\hspace{15pt}综上，可以计算得到选取期望为 \tfrac{5}{3}。我们能够找到，666\,666\,673 \times 3 = 2\,000\,000\,019，对 10^9+7 取模后恰好等于分子 5，所以 666\,666\,673 是需要输出的答案。