#pragma region kyopro_template #include #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template using V = vector; using vi = vector; using vl = vector; using vvi = vector>; using vd = V; using vs = V; using vvl = vector>; using P = pair; using vp = vector

; using pii = pair; using vpi = vector>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } void solve(); #ifdef NyaanDebug #include "NyaanDebug.h" #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) #else #define trc(...) #define trca(...) #define trcc(...) int main() { solve(); } #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template inline int getbit(T a, int i) { return (a >> i) & 1; } template inline void setbit(T &a, int i) { a |= (1LL << i); } template inline void delbit(T &a, int i) { a &= ~(1LL << i); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template vector mkrui(const vector &v) { vector ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v) { vector inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; #pragma endregion constexpr int MOD = /** 998244353; //*/ 1000000007; template >> struct HeavyLightDecomposition { G &g; int idx; vector size, depth, in, out, nxt, par; HeavyLightDecomposition(G &g, int root = 0) : g(g), idx(0), size(g.size(), 0), depth(g.size(), 0), in(g.size(), -1), out(g.size(), -1), nxt(g.size(), 0), par(g.size(), root) { dfs_sz(root); dfs_hld(root); } void build(int root) { dfs_sz(root); dfs_hld(root); } void dfs_sz(int cur) { size[cur] = 1; for (auto &dst : g[cur]) { if (dst == par[cur]) { if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]); else continue; } depth[dst] = depth[cur] + 1; par[dst] = cur; dfs_sz(dst); size[cur] += size[dst]; if (size[dst] > size[g[cur][0]]) { swap(dst, g[cur][0]); } } } void dfs_hld(int cur) { in[cur] = idx++; for (auto dst : g[cur]) { if (dst == par[cur]) continue; nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst)); dfs_hld(dst); } out[cur] = idx; } template void edge_query(int u, int v, const F &f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { if (u != v) f(in[u] + 1, in[v] + 1); break; } } } template void node_query(int u, int v, const F &f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { f(in[u], in[v] + 1); break; } } } template void sub_edge_query(int u, const F &f) { f(in[u] + 1, out[u]); } template void sub_node_query(int u, const F &f) { f(in[u], out[u]); } int lca(int a, int b) { while (nxt[a] != nxt[b]) { if (in[a] < in[b]) swap(a, b); a = par[nxt[a]]; } return depth[a] < depth[b] ? a : b; } }; // LazySegmentTree template struct LST { int n, height; F f; G g; H h; T ti; E ei; vector dat; vector laz; LST(int n, F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) { init(n); } LST(const vector &v, F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) { init((int)v.size()); build(v); } void init(int n_) { n = 1; height = 0; while (n < n_) n <<= 1, height++; dat.assign(2 * n, ti); laz.assign(2 * n, ei); } void build(const vector &v) { int n_ = v.size(); init(n_); for (int i = 0; i < n_; i++) dat[n + i] = v[i]; for (int i = n - 1; i; i--) dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]); } inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); } inline void eval(int k) { if (laz[k] == ei) return; laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]); laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]); dat[k] = reflect(k); laz[k] = ei; } inline void thrust(int k) { for (int i = height; i; i--) eval(k >> i); } inline void recalc(int k) { while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1)); } void update(int a, int b, E x) { thrust(a += n); thrust(b += n - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) laz[l] = h(laz[l], x), l++; if (r & 1) --r, laz[r] = h(laz[r], x); } recalc(a); recalc(b); } void set_val(int a, T x) { thrust(a += n); dat[a] = x; laz[a] = ei; recalc(a); } T query(int a, int b) { thrust(a += n); thrust(b += n - 1); T vl = ti, vr = ti; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) vl = f(vl, reflect(l++)); if (r & 1) vr = f(reflect(--r), vr); } return f(vl, vr); } }; template struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].pb(y); if (!is_directed) g[y].pb(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].eb(x, y, c); if (!is_directed) g[y].eb(y, x, c); } return g; } // Depth of Rooted Tree // unvisited nodes : d = -1 vector Depth(UnweightedGraph &g, int start = 0) { vector d(g.size(), -1); auto dfs = [&](auto rec, int cur, int par = -1) -> void { d[cur] = par == -1 ? 0 : d[par] + 1; each(dst, g[cur]) { if (dst == par) continue; rec(rec, dst, cur); } }; dfs(dfs, start); return d; } // Diameter of Tree pair Diameter(UnweightedGraph &g, int start = 0) { auto d = Depth(g, start); int u = max_element(begin(d), end(d)) - begin(d); d = Depth(g, u); int v = max_element(begin(d), end(d)) - begin(d); return make_pair(u, v); } template vector path(G &g, int u, int v) { vi ret; int end = 0; auto dfs = [&](auto rec, int cur, int par = -1) -> void { ret.pb(cur); if (cur == v) { end = 1; return; } each(dst, g[cur]) { if (dst == par) continue; rec(rec, dst, cur); if (end) return; } if (end) return; ret.pop_back(); }; dfs(dfs, u); return ret; } template struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return -ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(-r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * r) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt(t); return (is); } constexpr mint inverse() const { return pow(mod - 2); } static constexpr u32 get_mod() { return mod; } }; using mint = LazyMontgomeryModInt; using vm = vector; void solve() { ini(N); auto g = graph(N); HeavyLightDecomposition hld(g); vm e = {mint(1), mint(1), mint(2).inverse(), mint(6).inverse()}; auto mul = [](const vm &a, const vm &b) { vm c(sz(a) + sz(b) - 1); rep(i, sz(a)) rep(j, sz(b)) c[i + j] += a[i] * b[j]; return c; }; V ans(N); mint bns = 0; auto dfs = [&](auto rec, int cur, int par = -1) -> vm { ans[cur] = e; each(dst, g[cur]) { if (dst == par) continue; ans[cur] = mul(ans[cur], rec(rec, dst, cur)); ans[cur].resize(4); } trc(cur,hld.size[cur]); vm ret = ans[cur]; bns += ans[cur][3] * mint(6) * mint(2).pow(max(0, N - hld.size[cur] - 1)); ret[0] += mint(2).pow(hld.size[cur] - 1); return ret; }; dfs(dfs, 0); rep(i, N) ans[i][2] *= 2, ans[i][3] *= 6; trc(ans); out(bns); }