#include #include #include #include #include class UnionFind { public: UnionFind(const std::size_t v) : V(v), parent(v), size(v, 1) { std::iota(parent.begin(), parent.end(), 0); } std::size_t find(const std::size_t a) { return assert(a < V), parent[a] == a ? a : parent[a] = find(parent[a]); } bool same(const std::size_t a, const std::size_t b) { assert(a < V), assert(b < V); return find(a) == find(b); } void unite(std::size_t a, std::size_t b) { assert(a < V), assert(b < V); a = find(a), b = find(b); if (a == b) { return; } if (size[a] < size[b]) { std::swap(a, b); } size[a] += size[b], parent[b] = a; } std::size_t getSize(const std::size_t a) { return assert(a < V), size[find(a)]; } friend std::ostream& operator<<(std::ostream& os, const UnionFind& uf) { os << "["; for (std::size_t i = 0; i < uf.parent.size(); i++) { os << uf.parent[i] << (i + 1 == uf.parent.size() ? "" : ","); } return (os << "]\n"); } private: const std::size_t V; std::vector parent, size; }; template constexpr std::pair extgcd(const T a, const T b) { if (b == 0) { return std::pair{1, 0}; } const auto p = extgcd(b, a % b); return {p.second, p.first - p.second * (a / b)}; } template constexpr T inverse(const T a, const T mod) { return (mod + extgcd((mod + a % mod) % mod, mod).first % mod) % mod; } using uint = unsigned int; using ll = long long; using ull = unsigned long long; template class ModInt { private: uint v; static uint norm(const uint& x) { return x < mod ? x : x - mod; } static ModInt make(const uint& x) { ModInt m; return m.v = x, m; } static ModInt power(ModInt x, ll n) { ModInt ans = 1; for (; n; n >>= 1, x *= x) { if (n & 1) { ans *= x; } } return ans; } static ModInt inv(const ModInt& x) { return ModInt{inverse((ll)x.v, (ll)mod)}; } public: ModInt() : v{0} {} ModInt(const ll val) : v{norm(uint(val % (ll)mod + (ll)mod))} {} ModInt(const ModInt& n) : v{n()} {} explicit operator bool() const { return v != 0; } ModInt& operator=(const ModInt& n) { return v = n(), (*this); } ModInt& operator=(const ll val) { return v = norm(uint(val % (ll)mod + (ll)mod)), (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return make(norm(mod - v)); } ModInt operator+(const ModInt& val) const { return make(norm(v + val())); } ModInt operator-(const ModInt& val) const { return make(norm(v + mod - val())); } ModInt operator*(const ModInt& val) const { return make((uint)((ll)v * val() % (ll)mod)); } ModInt operator/(const ModInt& val) const { return *this * inv(val()); } ModInt& operator+=(const ModInt& val) { return *this = *this + val; } ModInt& operator-=(const ModInt& val) { return *this = *this - val; } ModInt& operator*=(const ModInt& val) { return *this = *this * val; } ModInt& operator/=(const ModInt& val) { return *this = *this / val; } ModInt operator+(const ll val) const { return ModInt{v + val}; } ModInt operator-(const ll val) const { return ModInt{v - val}; } ModInt operator*(const ll val) const { return ModInt{(ll)v * (val % mod)}; } ModInt operator/(const ll val) const { return ModInt{(ll)v * inv(val)}; } template ModInt operator^(const I n) const { return power(v, n); } ModInt& operator+=(const ll val) { return *this = *this + val; } ModInt& operator-=(const ll val) { return *this = *this - val; } ModInt& operator*=(const ll val) { return *this = *this * val; } ModInt& operator/=(const ll val) { return *this = *this / val; } template ModInt& operator^=(const I n) { return (*this) = ((*this) ^ n); } bool operator==(const ModInt& val) const { return v == val.v; } bool operator!=(const ModInt& val) const { return not(*this == val); } bool operator==(const ll val) const { return v == norm(uint((ll)mod + val % (ll)mod)); } bool operator!=(const ll val) const { return not(*this == val); } uint operator()() const { return v; } }; template inline ModInt operator+(const ll val, const ModInt& n) { return n + val; } template inline ModInt operator-(const ll val, const ModInt& n) { return ModInt{val - (ll)n()}; } template inline ModInt operator*(const ll val, const ModInt& n) { return n * val; } template inline ModInt operator/(const ll val, const ModInt& n) { return ModInt(val) / n; } template inline bool operator==(const ll val, const ModInt& n) { return n == val; } template inline bool operator!=(const ll val, const ModInt& n) { return not(val == n); } template inline std::istream& operator>>(std::istream& is, ModInt& n) { uint v; return is >> v, n = v, is; } template std::ostream& operator<<(std::ostream& os, const ModInt& n) { return (os << n()); } constexpr uint MOD = 1000000007; using mint = ModInt; mint ans = 0; void dfs(const std::vector>& G, const int s, const int p, const int d) { ans += mint(1) / (d + 1); for (const int to : G[s]) { if (to == p) { continue; } dfs(G, to, s, d + 1); } } int main() { int N; std::cin >> N; assert(0 <= N and N <= 200000); std::vector> G(N); UnionFind uf(N); for (int i = 0; i < N - 1; i++) { int u, v; std::cin >> u >> v; assert(0 <= u <= N); assert(0 <= v <= N); u--, v--; assert(not uf.same(u, v)); uf.unite(u, v); G[u].push_back(v), G[v].push_back(u); } dfs(G, 0, -1, 0); for (int i = 1; i <= N; i++) { ans *= i; } std::cout << ans << std::endl; return 0; }