#define task "tree" #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; constexpr int N = 1e6 + 5; ll Pow(ll a, ll b, ll mod); ll mod, p; pair gt[N], rgt[N]; int n, k; int cnt[N]; vector adj[N]; void Read() { cin >> n >> k >> p; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } } ll C(int k, int n) { if (k > n) return 0; if (gt[n].second + rgt[k].second + rgt[n - k].second > 0) return 0; return gt[n].first * rgt[k].first % mod * rgt[n - k].first % mod; } ll Cal(ll mods) { mod = mods; rgt[0] = gt[0] = make_pair(1, 0); for (int i = 1; i <= n; ++i) { ll v = i; gt[i] = gt[i - 1]; rgt[i] = rgt[i - 1]; while (v % mod == 0) { v /= mod; ++gt[i].second; --rgt[i].second; } (gt[i].first *= v) %= mod; rgt[i].first = v; } for (int i = 1; i <= n; ++i) rgt[i].first = rgt[i + 1].first; rgt[n].first = Pow(gt[n].first, mod - 2, mod); for (int i = n - 1; i; --i) (rgt[i].first *= rgt[i + 1].first) %= mod; ll ans(0); function GetAns = [&](int v, int p) { (ans += C(k, n - 1)) %= mod; cnt[v] = 1; for (auto i : adj[v]) if (i != p) { GetAns(i, v); cnt[v] += cnt[i]; (ans -= C(k, cnt[i])) %= mod; } (ans -= C(k, n - cnt[v])) %= mod; }; GetAns(1, -1); return (ans + mod) % mod; } void Sub_n() { if (p == 1019972207) cout << Cal(p); else { ll a1 = Cal(19), a2 = Cal(127), a3 = Cal(467), a4 = Cal(907); ll m1 = p / 19, m2 = p / 127, m3 = p / 467, m4 = p / 907; cout << (a1 * m1 * Pow(m1, 17, 19) + a2 * m2 * Pow(m2, 125, 127) + a3 * m3 * Pow(m3, 465, 467) + a4 * m4 * Pow(m4, 905, 907)) % p; } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task ".INP", "r")) { freopen(task ".INP", "r", stdin); freopen(task ".OUT", "w", stdout); } Read(); Sub_n(); } ll Pow(ll a, ll b, ll mod) { ll ans(1); for (; b > 0; b >>= 1) { if (b & 1) ans = ans * a % mod; a = a * a % mod; } return ans; }