Это сложная версия задачи. Единственное отличие в том, что в этой версии \(k\le n\). Вы можете делать взломы, только если обе версии задачи сданы.
Chtholly и летающие острова. LuoTianyi сейчас живёт в мире с \(n\) летающими островами. Летающие острова соединены \(n-1\) ненаправленной воздушной дорогой, и из любого из двух летающих островов можно добраться до другого, путешествуя по воздушным дорогам. Это означает, что \(n\) летающих островов образуют дерево.
Однажды, LuoTianyi захотела встретиться со своими друзьями: Chtholly, Nephren, William, .... Всего она хочет встретиться с \(k\) людьми. Она не знает их точного расположения, но она знает, что они находятся на попарно различных островах. Она называет остров хорошим тогда и только тогда, когда сумма расстояний\(^{\dagger}\) от него до островов с \(k\) людьми минимально возможная среди всех \(n\) островов.
Сейчас LuoTianyi хочет узнать, если \(k\) человек случайным образом находятся в \(k\) различных из \(n\) островов, чему равно математическое ожидание количества хороших островов? Вам нужно сказать ей математическое ожидание по модулю \(10^9+7\).
\(^{\dagger}\)Расстоянием между двумя островами называется минимальное количество воздушных дорог, по которым нужно пройти, чтобы перейти с одного острова на другой.
Выходные данные
Выведите единственное целое число — математическое ожидание количества хороших островов по модулю \(10^9 + 7\).
Формально, пусть \(M = 10^9 + 7\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0\) (\(\operatorname{mod} M\)). Выведите целое число, равное \(p \cdot q^{-1}\) \(\operatorname{mod} M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p\) (\(\operatorname{mod} M\)).
Примечание
В первом примере дороги образуют следующее дерево:
Если люди находятся на островах \(1\) и \(2\), тогда острова \(1\) и \(2\) являются хорошими.
Сумма расстояний от острова \(1\) или \(2\) до всех людей равна \(1+0=1\), что минимально. В это время сумма расстояний от острова \(3\) до всех людей равна \(2+1=3\), что больше \(1\).
Таким же образом, когда люди находятся на островах \(1\) и \(3\), тогда острова \(1,2\) и \(3\) являются хорошими.
Когда люди находятся на островах \(1\) и \(4\), тогда острова \(1,2,3\) и \(4\) являются хорошими.
Когда люди находятся на островах \(2\) и \(3\), тогда острова \(2\) и \(3\) являются хорошими.
Когда люди находятся на островах \(2\) и \(4\), тогда острова \(2,3\) и \(4\) являются хорошими.
Когда люди находятся на островах \(3\) и \(4\), тогда острова \(3\) и \(4\) являются хорошими.
Поэтому математическое ожидание количества хороших островов равно \(\frac{16}{6}\), что равняется \(666666674\) по модулю \(10^9+7\).
Во втором примере дороги образуют следующее дерево:
Мы можем заметить, что так как есть один человек на каждом острове, то только остров \(3\) является хорошим. Поэтому математическое ожидание количества хороших островов равно \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
2 3
3 4
|
666666674
|
|
2
|
5 5
1 2
2 3
3 4
3 5
|
1
|