fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int const N=200001,mod=1e9+7;
  4. long long ods[N],sil[N],dp[N],zm;
  5. int roz[N];
  6. bool odw[N];
  7. vector<int>g[N];
  8.  
  9. long long dwu(int n, int k){
  10. if(k>n) swap(n,k);
  11. //cout<<sil[n+1]<<' '<<ods[k]<<' '<<ods[n-k+1]<<endl;
  12. return ((long long)sil[n+1]*ods[k]%mod*ods[n-k+1])%mod;
  13. }
  14.  
  15. void dfs(int v){
  16. odw[v]=1;
  17. dp[v]=1;
  18. for(int i:g[v]){
  19. if(odw[i]==0){
  20. dfs(i);
  21. dp[v]=dwu(roz[v],roz[i])*dp[v]%mod*dp[i]%mod;
  22. //cout<<i<<' '<<dwu(roz[v],roz[i])<<endl;
  23. roz[v]+=roz[i];
  24. }
  25.  
  26. }
  27. roz[v]++;
  28. //cout<<v<<' '<<dp[v]<<endl;;
  29. }
  30.  
  31. long long pot(int base,int wyk){
  32. //cout<<base<<' '<<wyk<<endl;
  33. if(wyk==0) return 1;
  34. if(wyk==1) return base;
  35. if(wyk%2==0){
  36. zm=pot(base,wyk/2);
  37. //cout<<(zm*zm)%mod<<endl;
  38. return (zm*zm)%mod;
  39. }
  40. zm=(pot(base,wyk-1)*base)%mod;
  41. //cout<<zm<<endl;
  42. return zm;
  43. }
  44.  
  45. int main(){
  46. ios_base::sync_with_stdio(0);
  47. cin.tie(0);
  48. int n,a,b;
  49. cin>>n;
  50. sil[0]=1;
  51. ods[0]=1;
  52. //cout<<pot(2,mod-2);
  53. for(int i=1;i<=n;i++) {sil[i]=((long long)sil[i-1]*i)%mod; ods[i]=pot(sil[i],mod-2);}
  54. for(int i=1;i<n;i++){
  55. cin>>a>>b;
  56. g[a].push_back(b);
  57. g[b].push_back(a);
  58. }
  59. dfs(1);
  60. cout<<dp[1];
  61. }
  62.  
Success #stdin #stdout 0.01s 13300KB
stdin
5
2 4
3 4
5 1
4 1
stdout
8