考虑累加种下第 \(i\) 棵不同的树树到种下第 \(i+1\) 棵不同的树之间的时间间隔，设 \(f(i)\) 表示种了 \(i\) 棵不同的树游戏仍未结束的概率，那么有：
\[\begin{aligned} ans&=\sum_{i=0}^{n-1}f(i)\left(\sum_{t=0}^{\infty}\left(\frac{i}{n}\right)^t\left(1-\frac{i}{n}\right)(t+1)\right)\\ &=\sum_{i=0}^{n-1}\frac{n}{n-i}f(i) \end{aligned} \]设 \(g(i)\) 表示恰好在种了 \(i\) 棵不同的树时游戏结束的概率，那么有 \(f(i)=1-\sum_{j\leq i}g(j)\)。
考虑恰好在种了 \(i\) 棵不同的树时游戏结束的情形会是怎样：有 \(i\) 个位置是我们种的树，剩下 \(n-i\) 个位置是它们自己长出来的（称这些位置为空位置），我们需要保证这 \(n-i\) 个空位置不能相邻（否则长不出来）。把符合这种条件的游戏情形称为 ”结束情形“。
考虑先把这 \(n-i\) 个位置选出来，概率为 \(\dfrac{\binom{i}{n-i}}{\binom{n-1}{i-1}}\)。
当然也有可能一些本来我们要种树的地方它自己长出来了，导致游戏提前结束，所以这部分的概率要剪掉。而发现当存在空位置相邻时游戏一定不可能结束，所以（在我们限制的情形下，游戏提前结束的概率）就等于（游戏提前结束的概率），即游戏不可能在我们限制的情形之外提前结束，于是直接减掉 \(\sum_{j<i}g(j)\) 即可，即：
\[g(i)=\dfrac{\binom{i}{n-i}}{\binom{n-1}{i-1}}-\sum_{j<i}g(j) \]你发现 \(f(i)\) 刚好等于 \(\dfrac{\binom{i}{n-i}}{\binom{n-1}{i-1}}\)，即把 \(n-i\) 个位置选出来的概率。
另一种解释是：考虑在所有树都长出来的情况下 ”宣布“ 游戏结束，但仍能继续种树，那么之后无论我怎么种树总是满足 ”结束情形“ 的要求。所以前 \(i\) 轮中 ”宣布“ 了游戏结束的概率就等于第 \(i\) 轮时的情形满足 ”结束情形“ 要求的概率。
#include<bits/stdc++.h>
#define N 10000010
using namespace std;
namespace modular
{
const int mod=1000000007;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
}using namespace modular;
inline int poww(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,fac[N],ifac[N];
inline int inv(int x)
{
return mul(ifac[x],fac[x-1]);
}
inline int C(int n,int m)
{
return mul(mul(fac[n],ifac[m]),ifac[n-m]);
}
inline int invC(int n,int m)
{
return mul(mul(ifac[n],fac[m]),fac[n-m]);
}
int main()
{
n=read();
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=poww(fac[n],mod-2);
for(int i=n;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
int ans=0;
for(int i=0;i<n;i++)
Add(ans,mul(inv(n-i),i>=n-(n/2)?dec(1,mul(C(i,n-i),invC(n-1,i-1))):1));
printf("%d\n",mul(ans,n));
return 0;
}