#include #include #include using namespace std; constexpr int mod=1e9+7; constexpr int N = 2e5; int now; int parent[N],head[N],vid[N],sub[N],s[N],w[N]; vector g[N]; int64_t s0[N+1],s1[N+1],sw[N+1]; int in(){int n;scanf("%d",&n);return n;} void dfs(int u,int p){ sub[u]=1;for(int v:g[u])if(v!=p)dfs(v,u),sub[u]+=sub[v]; } void dfs2(int u,int p,int h){ parent[u]=p;head[u]=h;vid[u]=now++; for(int v:g[u])if(v!=p&&sub[u]=sub[v]*2)dfs2(v,u,v); } template void foreach(int u,int v,T f){ for(;;v=parent[head[v]]){ if(vid[u]>vid[v])swap(u,v); if(head[u]==head[v])return f(vid[u],vid[v]); f(vid[head[v]],vid[v]); } } void add(int k,int64_t v){ for(int i=k+1;i<=N;i+=i&-i)s0[i]+=mod-v*sw[k]%mod,s1[i]+=v; } void add_point(int k,int64_t v){ for(int i=k+1;i<=N;i+=i&-i)s0[i]+=v; } int64_t sum(int k){ int64_t ret0=0,ret1=0; for(int i=k;i>0;i-=i&-i)ret0+=s0[i],ret1+=s1[i]; return (ret0+ret1%mod*sw[k])%mod; } int main() { int n=in(); for(int i=0;i