#include <bits/stdc++.h> #define LL long long #define lson pos<<1 #define rson pos<<1|1 using namespace std; const int MAXN=1e6+5,MOD=1e9+7; int N; LL po[MAXN]; LL ans[MAXN]; LL t[MAXN]; LL inv[MAXN]; LL QPow(LL base,int po) { LL res=1; while(po) { if(po&1) res=res*base%MOD; base=base*base%MOD; po>>=1; } return res; } struct SegTree { LL sum,tag; }tre[MAXN<<2]; void PushUp(int pos) { tre[pos].sum=(tre[lson].sum+tre[rson].sum)%MOD; return; } void Build(int pos,int l,int r) { tre[pos]={0,0}; if(l==r) { tre[pos].sum=0; return; } int mid=(l+r)>>1; Build(lson,l,mid); Build(rson,mid+1,r); PushUp(pos); return; } void Update(int pos,int l,int r,int ql,int qr,int k) { tre[pos].sum+=k*(qr-ql+1); tre[pos].sum%=MOD; if(ql<=l&&r<=qr) { tre[pos].tag+=k; tre[pos].tag%=MOD; return; } int mid=(l+r)>>1; if(ql<=mid) Update(lson,l,mid,ql,min(qr,mid),k); if(mid<qr) Update(rson,mid+1,r,max(ql,mid+1),qr,k); return; } int Query(int pos,int l,int r,int ql,int qr,int tags) { if(ql<=l&&r<=qr) { return (tre[pos].sum+tags*(qr-ql+1))%MOD; } tags+=tre[pos].tag; tags%=MOD; int mid=(l+r)>>1; int res=0; if(ql<=mid) res+=Query(lson,l,mid,ql,min(qr,mid),tags); if(mid<qr) res+=Query(rson,mid+1,r,max(ql,mid+1),qr,tags); return res; } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d",&N); if(N==1) { puts("2"); return 0; } po[0]=1; for(int i=1;i<=N;i++) po[i]=(po[i-1]<<1)%MOD; for(int i=2;i<=N;i++) { int fr=(i+1)/2; ans[i]=po[i-fr]; ans[i]=ans[i]*po[N-i]%MOD; t[i]=po[N-i]; } Build(1,1,N); ans[N]=ans[N]*2%MOD; for(int i=1;i<=N;i++) inv[i]=QPow(po[i],MOD-2); for(int i=N;i>=2;i--) { int fr=(i+1)/2; if(i!=N) { ans[i]=ans[i]*QPow(t[i],MOD-2)%MOD; t[i]=(t[i]-Query(1,1,N,i,i,0)*inv[i]%MOD+MOD)%MOD; ans[i]=ans[i]*t[i]%MOD; } Update(1,1,N,2,i-fr,ans[i]); } LL S=0; for(int i=2;i<=N;i++) S+=ans[i]*i%MOD; printf("%lld\n",S%MOD); return 0; }