水题,逆推一遍即可~
code:
#include <bits/stdc++.h> #define N 12000010 #define LL long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; const LL mod=1000000007; int inv[N]; int main() { // setIO("input"); int n,i; scanf("%d",&n); LL f=0,s=0; inv[1]=1; for(i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(i=n-1;i>=1;--i) { f=((s+1ll*n-1ll*i+1ll)*inv[n-i]%mod)%mod, s=(s+f)%mod; } printf("%lld\n",f); return 0; }