Language: C++

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

template<int MOD = 1000000007>
struct mod_int {
    int val;
    mod_int(long long val_ = 0) : val(val_ % MOD) { if (val < 0) { val += MOD; }}
    bool operator==(const mod_int &rhs) const { return val == rhs.val; }
    bool operator!=(const mod_int &rhs) const { return std::rel_ops::operator!=(*this, rhs); }
    mod_int &operator+=(const mod_int &rhs) {
        if ((val += rhs.val) >= MOD) { val -= MOD; }
        return *this;
    }
    mod_int &operator-=(const mod_int &rhs) {
        if ((val += MOD - rhs.val) >= MOD) { val -= MOD; }
        return *this;
    }
    mod_int &operator*=(const mod_int &rhs) {
        val = (int) ((long long) val * rhs.val % MOD);
        return *this;
    }
    mod_int &operator/=(const mod_int &rhs) { return *this *= rhs.inv(); }
    mod_int operator+() const { return *this; }
    mod_int operator-() const { return -val; }
    mod_int operator++() { return *this += 1; }
    mod_int operator--() { return *this -= 1; }
    mod_int operator++(signed) {
        const mod_int ret(*this);
        ++*this;
        return ret;
    }
    mod_int operator--(signed) {
        const mod_int ret(*this);
        --*this;
        return ret;
    }
    mod_int operator+(const mod_int &rhs) const { return mod_int(*this) += rhs; }
    mod_int operator-(const mod_int &rhs) const { return mod_int(*this) -= rhs; }
    mod_int operator*(const mod_int &rhs) const { return mod_int(*this) *= rhs; }
    mod_int operator/(const mod_int &rhs) const { return mod_int(*this) /= rhs; }
    mod_int inv() const {
        assert(val != 0);
        int a = val, b = MOD, x = 1, u = 0;
        while (b) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(x -= t * u, u);
        }
        return x;
    }
    mod_int pow(long long n) const {
        if (n < 0) { return pow(-n).inv(); }
        mod_int ret = 1, mul = *this;
        while (n) {
            if (n & 1) { ret *= mul; }
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend std::istream &operator>>(std::istream &is, mod_int &rhs) {
        long long v;
        is >> v;
        rhs = v;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const mod_int &rhs) { return os << rhs.val; }
    struct combination {
        std::vector<mod_int> fact{1, 1}, f_inv{1, 1}, inv{0, 1};
        void calc(int n) {
            while (fact.size() <= n) {
                int i = fact.size();
                fact.push_back(fact[i - 1] * i);
                inv.push_back(-inv[MOD % i] * (MOD / i));
                f_inv.push_back(f_inv[i - 1] * inv[i]);
            }
        }
        mod_int P(int n, int r) { return r < 0 || n < r ? 0 : (calc(n), fact[n] * f_inv[n - r]); }
        mod_int C(int n, int r) { return r < 0 || n < r ? 0 : (calc(n), fact[n] * f_inv[r] * f_inv[n - r]); }
        mod_int H(int n, int r) { return C(n + r - 1, r); }
    };
};

template<typename T> void fft(std::vector<T> &x, const std::vector<T> &w) {
    int n = x.size();
    int m = n >> 1;
    std::vector<T> y(n);
    std::vector<T> *p = &x, *q = &y;
    for (int i = 1; i <= m; i <<= 1) {
        for (int j = 0; j < m; j += i) {
            for (int k = 0; k < i; k++) {
                int u = j + k;
                (*q)[(u << 1) + 0] = ((*p)[u + 0] + (*p)[u + m]);
                (*q)[(u << 1) + 1] = ((*p)[u + 0] - (*p)[u + m]) * w[j];
            }
        }
        std::swap(p, q);
    }
    if (p != &x) { std::copy(p->begin(), p->end(), x.begin()); }
}

template<typename T> void ifft(std::vector<T> &x, const std::vector<T> &w) {
    int n = x.size();
    int m = n >> 1;
    std::vector<T> y(n);
    std::vector<T> *p = &x, *q = &y;
    for (int i = m; i > 0; i >>= 1) {
        for (int j = 0; j < m; j += i) {
            for (int k = 0; k < i; k++) {
                int u = j + k;
                (*p)[(u << 1) + 1] *= w[j];
                (*q)[u + 0] = (*p)[(u << 1) + 0] + (*p)[(u << 1) + 1];
                (*q)[u + m] = (*p)[(u << 1) + 0] - (*p)[(u << 1) + 1];
            }
        }
        std::swap(p, q);
    }
    T n_inv = T(1) / n;
    for (int i = 0; i < n; i++) { x[i] = (*p)[i] * n_inv; }
}

template<int MOD, int ROOT>
std::vector<int> friendly_mod_convolute(const std::vector<int> &a, const std::vector<int> &b) {
    int n_a = a.size(), n_b = b.size();
    int n_ = n_a + n_b - 1, n;
    for (n = 1; n < n_; n <<= 1) {}
    int m = n >> 1;
    std::vector<mod_int<MOD>> a_mint(n), b_mint(n), w(m + 2);
    std::copy(a.begin(), a.end(), a_mint.begin()), std::copy(b.begin(), b.end(), b_mint.begin());
    w[0] = 1, w[1] = mod_int<MOD>(ROOT).pow((MOD - 1) / n);
    for (int i = 2; i < m; i++) { w[i] = w[i - 1] * w[1]; }
    fft(a_mint, w);
    fft(b_mint, w);
    for (int i = 0; i < n; i++) { a_mint[i] *= b_mint[i]; }
    w[1] = w[1].inv();
    for (int i = 2; i < m; i++) { w[i] = w[i - 1] * w[1]; }
    ifft(a_mint, w);
    std::vector<int> ret(n_);
    for (int i = 0; i < n_; i++) { ret[i] = a_mint[i].val; }
    return ret;
}

template<int K = 3>
std::vector<int> arbitrary_mod_convolute(const std::vector<int> &a, const std::vector<int> &b, int mod) {
    static constexpr int MS[] = {998244353, 469762049, 167772161}, RS[] = {3, 3, 3};
    static auto safe_mod = [](int a, int m) -> int {
        a %= m;
        if (a < 0) { a += m; }
        return a;
    };
    static auto mod_inv = [](int a, int m) -> int {
        int b = m, x = 1, u = 0;
        while (b) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(x -= t * u, u);
        }
        return safe_mod(x, m);
    };
    int n_a = a.size(), n_b = b.size();
    int n_ = n_a + n_b - 1, n;
    for (n = 1; n < n_; n <<= 1) {}
    std::vector<int> m(K + 1), prod_m(K + 1, 1);
    std::vector<std::vector<int>> ret(K + 1, std::vector<int>(n_));
    std::copy(MS, MS + K, m.begin());
    m[K] = mod;
    for (int i = 0; i < K; i++) {
        std::vector<int> piece;
        if (i == 0) { piece = friendly_mod_convolute<MS[0], RS[0]>(a, b); }
        if (i == 1) { piece = friendly_mod_convolute<MS[1], RS[1]>(a, b); }
        if (i == 2) { piece = friendly_mod_convolute<MS[2], RS[2]>(a, b); }
        int prod_inv = mod_inv(prod_m[i], m[i]);
        for (int j = 0; j < n_; j++) {
            int mod_m_i = (long long) safe_mod(piece[j] - ret[i][j], m[i]) * prod_inv % m[i];
            for (int k = i + 1; k <= K; k++) {
                ret[k][j] = (ret[k][j] + (long long) mod_m_i * prod_m[k] % m[k]) % m[k];
            }
        }
        for (int j = i + 1; j <= K; j++) { prod_m[j] = (long long) prod_m[j] * m[i] % m[j]; }
    }
    return ret[K];
}

template<int mod>
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if ((x += p.x) >= mod) { x -= mod; }
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if ((x += mod - p.x) >= mod) { x -= mod; }
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while (n > 0) {
            if (n & 1) { ret *= mul; }
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

namespace FastFourierTransform {
    using real = double;

    struct C {
        real x, y;

        C() : x(0), y(0) {}

        C(real x, real y) : x(x), y(y) {}

        inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }

        inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }

        inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }

        inline C conj() const { return C(x, -y); }
    };

    const real PI = acosl(-1);
    int base = 1;
    vector<C> rts = {{0, 0},
                     {1, 0}};
    vector<int> rev = {0, 1};

    void ensure_base(int nbase) {
        if (nbase <= base) { return; }
        rev.resize(1 << nbase);
        rts.resize(1 << nbase);
        for (int i = 0; i < (1 << nbase); i++) {
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
        }
        while (base < nbase) {
            real angle = PI * 2.0 / (1 << (base + 1));
            for (int i = 1 << (base - 1); i < (1 << base); i++) {
                rts[i << 1] = rts[i];
                real angle_i = angle * (2 * i + 1 - (1 << base));
                rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
            }
            ++base;
        }
    }

    void fft(vector<C> &a, int n) {
        assert((n & (n - 1)) == 0);
        int zeros = __builtin_ctz(n);
        ensure_base(zeros);
        int shift = base - zeros;
        for (int i = 0; i < n; i++) {
            if (i < (rev[i] >> shift)) {
                swap(a[i], a[rev[i] >> shift]);
            }
        }
        for (int k = 1; k < n; k <<= 1) {
            for (int i = 0; i < n; i += 2 * k) {
                for (int j = 0; j < k; j++) {
                    C z = a[i + j + k] * rts[j + k];
                    a[i + j + k] = a[i + j] - z;
                    a[i + j] = a[i + j] + z;
                }
            }
        }
    }

    vector<int64_t> multiply(const vector<int> &a, const vector<int> &b) {
        int need = (int) a.size() + (int) b.size() - 1;
        int nbase = 1;
        while ((1 << nbase) < need) { nbase++; }
        ensure_base(nbase);
        int sz = 1 << nbase;
        vector<C> fa(sz);
        for (int i = 0; i < sz; i++) {
            int x = (i < (int) a.size() ? a[i] : 0);
            int y = (i < (int) b.size() ? b[i] : 0);
            fa[i] = C(x, y);
        }
        fft(fa, sz);
        C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
        for (int i = 0; i <= (sz >> 1); i++) {
            int j = (sz - i) & (sz - 1);
            C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
            fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
            fa[i] = z;
        }
        for (int i = 0; i < (sz >> 1); i++) {
            C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
            C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
            fa[i] = A0 + A1 * s;
        }
        fft(fa, sz >> 1);
        vector<int64_t> ret(need);
        for (int i = 0; i < need; i++) {
            ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
        }
        return ret;
    }
};

using modint = ModInt<1000000007>;

template<typename T>
struct ArbitraryModConvolution {
    using real = FastFourierTransform::real;
    using C = FastFourierTransform::C;

    ArbitraryModConvolution() = default;

    vector<int> multiply(const vector<int> &a, const vector<int> &b, int need = -1) {
        if (need == -1) { need = a.size() + b.size() - 1; }
        int nbase = 0;
        while ((1 << nbase) < need) { nbase++; }
        FastFourierTransform::ensure_base(nbase);
        int sz = 1 << nbase;
        vector<C> fa(sz);
        for (int i = 0; i < a.size(); i++) {
            fa[i] = C(a[i] & ((1 << 15) - 1), a[i] >> 15);
        }
        fft(fa, sz);
        vector<C> fb(sz);
        if (a == b) {
            fb = fa;
        } else {
            for (int i = 0; i < b.size(); i++) {
                fb[i] = C(b[i] & ((1 << 15) - 1), b[i] >> 15);
            }
            fft(fb, sz);
        }
        real ratio = 0.25 / sz;
        C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
        for (int i = 0; i <= (sz >> 1); i++) {
            int j = (sz - i) & (sz - 1);
            C a1 = (fa[i] + fa[j].conj());
            C a2 = (fa[i] - fa[j].conj()) * r2;
            C b1 = (fb[i] + fb[j].conj()) * r3;
            C b2 = (fb[i] - fb[j].conj()) * r4;
            if (i != j) {
                C c1 = (fa[j] + fa[i].conj());
                C c2 = (fa[j] - fa[i].conj()) * r2;
                C d1 = (fb[j] + fb[i].conj()) * r3;
                C d2 = (fb[j] - fb[i].conj()) * r4;
                fa[i] = c1 * d1 + c2 * d2 * r5;
                fb[i] = c1 * d2 + c2 * d1;
            }
            fa[j] = a1 * b1 + a2 * b2 * r5;
            fb[j] = a1 * b2 + a2 * b1;
        }
        fft(fa, sz);
        fft(fb, sz);
        vector<int> ret(need);
        for (int i = 0; i < need; i++) {
            T aa = llround(fa[i].x);
            T bb = llround(fb[i].x);
            T cc = llround(fa[i].y);
            ret[i] = (aa + (bb * bit(15)) + (cc * bit(30))).x;
        }
        return ret;
    }
};

struct union_find_tree {
    std::vector<int> par, size;
    union_find_tree(int n) : par(n), size(n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            size[i] = 1;
        }
    }
    int get_root(int i) {
        if (par[i] == i) { return i; }
        else { return par[i] = get_root(par[i]); }
    }
    void unite(int i, int j) {
        if ((i = get_root(i)) == (j = get_root(j))) { return; }
        if (size[i] < size[j]) { std::swap(i, j); }
        par[j] = i;
        size[i] += size[j];
    }
    bool are_same(int i, int j) { return get_root(i) == get_root(j); }
    int get_size(int i) { return size[get_root(i)]; }
};

int N;
int x[5500], y[5500];
vvint G;
constexpr int MOD = 1e9 + 7;
using mint = mod_int<MOD>;
mint::combination comb;
union_find_tree uf(0);
ArbitraryModConvolution<modint> conv;
vint operator+(const vint &a, const vint &b) {
    int sz = max(a.size(), b.size());
    vint ret(sz);
    copy(all(a), ret.begin());
    rep(i, b.size()) { (ret[i] += b[i]) %= MOD; }
    return ret;
}
vint operator*(const vint &a, int b) {
    vint ret(a);
    rep(i, ret.size()) { (ret[i] *= b) %= MOD; }
    return ret;
}
pair<vint, vint> dfs(int cur, int par) {
    vint ret0(uf.size[cur] / 2 + 1), ret1{0};
    ret0[uf.size[cur] / 2] = 1;
    rep(i, G[cur].size()) {
        if (G[cur][i] == par) { continue; }
        pair<vint, vint> nxt = dfs(G[cur][i], cur);
        int sum0 = 0, sum1 = 0;
        mint inv2 = mint(2).inv();
        mint p = 1;
        rep(j, nxt.first.size()) {
            (sum0 += (comb.fact[j * 2] * p * comb.f_inv[j] * nxt.first[j]).val) %= MOD;
            p *= inv2;
        }
        p = 1;
        rep(j, nxt.second.size()) {
            (sum1 += (comb.fact[j * 2] * p * comb.f_inv[j] * nxt.second[j]).val) %= MOD;
            p *= inv2;
        }
        vint tmp0 = conv.multiply(ret0, nxt.first) + conv.multiply(ret1, nxt.second) + ret0 * sum1 + ret1 * sum0;
        vint tmp1 = conv.multiply(ret0, nxt.second) + conv.multiply(ret1, nxt.first) + ret0 * sum0 + ret1 * sum1;
        ret0 = tmp0, ret1 = tmp1;
    }
    return {ret0, ret1};

}
signed main() {
    cin >> N;
    conb.calc(N);
    G.resize(N);
    uf = union_find_tree(N);
    vvint g(N);
    vint sz(N, 1), deg(N);
    rep(i, N - 1) {
        cin >> x[i] >> y[i];
        x[i]--, y[i]--;
        g[x[i]].push_back(y[i]), g[y[i]].push_back(x[i]);
        deg[x[i]]++, deg[y[i]]++;
    }
    queue<int> q;
    rep(i, N) { if (deg[i] == 1) { q.push(i); }}
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        deg[cur] = 0;
        rep(i, g[cur].size()) {
            int nxt = g[cur][i];
            if (deg[nxt] == 0) { continue; }
            if (sz[cur] & 1) { uf.unite(cur, nxt); }
            deg[nxt]--;
            if (deg[nxt] == 1) { q.push(nxt); }
            sz[nxt] += sz[cur];
        }
    }
    rep(i, N - 1) {
        if (uf.are_same(x[i], y[i])) { continue; }
        int u = uf.get_root(x[i]), v = uf.get_root(y[i]);
        G[u].push_back(v), G[v].push_back(u);
    }
    pair<vint, vint> pv = dfs(uf.get_root(0), -1);
    mint ans = 0;
    rep(i, pv.first.size()) { ans += comb.P(i * 2, i * 2) / mint(2).pow(i) / comb.P(i, i) * pv.first[i]; }
    rep(i, pv.second.size()) { ans -= comb.P(i * 2, i * 2) / mint(2).pow(i) / comb.P(i, i) * pv.second[i]; }
    cout << ans << endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:547:5: error: 'conb' was not declared in this scope; did you mean 'conv'?
  547 |     conb.calc(N);
      |     ^~~~
      |     conv