#include #include #include #include #include #include #include using namespace std; const int N=200000,mod=1000000007; int jc[N],ny[N],head[N],d[N],tot,nxt[N],to[N],ww[N],ans,dp[N]; bool b[N],vis[N]; void add(int u,int v,int w) { nxt[tot]=head[u]; to[tot]=v; ww[tot]=w; head[u]=tot++; d[v]++; } void dfs(int u) { int i,cnt,v,w; vis[u]=1; dp[u]=0; for (i=head[u];i>-1;i=nxt[i]) { v=to[i]; w=ww[i]; if (vis[v]) continue; dfs(v); if (b[w]) { ans=(ans+dp[v])%mod; dp[v]=mod-1; } ans=(ans-(long long)dp[u]*dp[v]%mod*ny[d[u]-1]%mod+mod)%mod; dp[u]=(dp[u]+dp[v])%mod; } dp[u]=(long long)dp[u]*ny[d[u]-1]%mod; } int read() { char c; int i; do c=getchar(); while (c<'0'||c>'9'); for (i=0;c>='0'&&c<='9';c=getchar()) i=i*10+c-'0'; return i; } int main() { freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int i,c,T,n,k,u,v,e,a; jc[0]=1; for (i=1;i1) a=(long long)a*jc[d[i]-1]%mod; ans=k; dfs(1); printf("%d\n",(long long)a*ans%mod); } return 0; }