//Just Remember 21 // It finally goes to an end. // AK and AFO. // #include using namespace std; const int N = 5e5+7; const int mod = 1e9+7; template inline void read(T &x) { x=0;char c=getchar();bool f=0; for(;c<'0'||c>'9';c=getchar())f|=(c=='-'); for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0'; x=(f?-x:x); } int n,k; vector > G[N]; bool vis[N]; int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; } int fac[N],inv[N],val[N]; int f[N],ans=1,res=0; void dfs(int x,int pre) { f[x]=0; for(auto u:G[x])if(u.first!=pre) { int y=u.first; dfs(y,x); if(vis[u.second])res=(res+f[y])%mod,f[y]=1; res=(res+1ll*f[x]*f[y]%mod*val[x]%mod)%mod; f[x]=(f[x]+f[y])%mod; } f[x]=1ll*f[x]*val[x]%mod; } void solve() { read(n);read(k); for(int i=1;i<=n;i++)G[i].clear(); for(int i=1;i1) ans=1ll*ans*fac[G[i].size()-1]%mod; dfs(1,0); res=1ll*res*ans%mod; ans=1ll*ans*k%mod; ans=(ans-res+mod)%mod; printf("%d\n",ans); } int main() { freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int c,T; read(c);read(T); fac[0]=1; for(int i=1;i