#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const ll MOD=1e9+7; const ll inv2=5e8+4; vector g[300030]; ll ans; ll dp[300030]; void dfs(int x, int p){ ll s=0; for(auto y:g[x]){ if(y==p) continue; dfs(y, x); ll z=inv2*dp[y]%MOD; (dp[x]+=z)%=MOD; (s+=z*z)%=MOD; } (ans+=dp[x]*6)%=MOD; (ans+=(dp[x]*dp[x]-s+MOD)*3)%=MOD; dp[x]=(dp[x]+1)%MOD; } ll dp2[300030]; const ll inv6=(MOD+1)/6; const ll inv8=(MOD+1)/8; void dfs2(int x, int p){ ll s=0; for(auto y:g[x]){ if(y==p) continue; (s+=dp[y])%=MOD; } for(auto y:g[x]){ if(y==p) continue; dp2[y]=(1+inv2*(s-dp[y]+dp2[x]))%MOD; } ll s1=0, s2=0, s3=0; for(auto y:g[x]){ if(y==p){ (s1+=dp2[x])%=MOD; (s2+=dp2[x]*dp2[x])%=MOD; (s3+=dp2[x]*dp2[x]%MOD*dp2[x])%=MOD; }else{ (s1+=dp[y])%=MOD; (s2+=dp[y]*dp[y])%=MOD; (s3+=dp[y]*dp[y]%MOD*dp[y])%=MOD; } } (ans+=(s1*s1-s2+MOD)%MOD*inv8%MOD*6)%=MOD; (ans+=(s1*s1%MOD*s1+2*s3-3*s2*s1%MOD+MOD)%MOD*inv8%MOD)%=MOD; for(auto y:g[x]){ if(y==p) continue; dfs2(y, x); } } int main() { int n; cin>>n; if(n==1){ cout<<1<>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } ans=n; dfs(0, -1); dfs2(0, -1); for(int i=0; i