У Ими есть неориентированное дерево из \(n\) вершин, ребра которого пронумерованы от \(1\) до \(n-1\). \(i\)-е ребро соединят вершины \(u_i\) и \(v_i\). Также на дереве находятся \(k\) бабочек. Изначально \(i\)-я бабочка находится в вершине \(a_i\). Все значения \(a\) попарно различны.
Косия играет в игру следующим образом.
- Для \(i = 1, 2, \dots, n - 1\) Косия выбирает одно из направлений \(i\)-го ребра (\(u_i \rightarrow v_i\) или \(v_i \rightarrow u_i\)) с одинаковой вероятностью.
- Для \(i = 1, 2, \dots, n - 1\), если в начальной вершине \(i\)-го ребра есть бабочка, а в конечной вершине нет бабочки, то эта бабочка перелетает в конечную вершину. Обратите внимание, что операции выполняются для ребер \(1, 2, \dots, n - 1\) по порядку, а не одновременно.
- Косия выбирает две бабочки из \(k\) бабочек с равной вероятностью для всех \(\frac{k(k-1)}{2}\) способов выбрать две бабочки, затем она вычисляет расстояние\(^\dagger\) между двумя вершинами, и объявляет это своим счетом.
Косия хочет, чтобы вы вычислили математическое ожидание ее счета по модулю \(998\,244\,353^\ddagger\).
\(^\dagger\) Расстоянием между двумя вершинами в дереве называется количество ребер на (единственном) простом пути между ними.
\(^\ddagger\) Формально, пусть \(M = 998\,244\,353\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).
Выходные данные
Выведите одно целое число — математическое ожидание счета Косии по модулю \(998\,244\,353\).
Примечание
Дерево из первого примера показано ниже. Вершины с бабочками отмечены жирным.
Существуют только \(2\) бабочки, поэтому выбор бабочек фиксирован. Рассмотрим следующие \(4\) случая:
- Ориентация ребер \(1 \rightarrow 2\) и \(2 \rightarrow 3\): бабочка из вершины \(1\) перемещается в вершину \(2\), а бабочка в вершине \(3\) не двигается. Расстояние между вершинами \(2\) и \(3\) равно \(1\).
- Ориентация ребер \(1 \rightarrow 2\) и \(3 \rightarrow 2\): бабочка из вершины \(1\) перемещается в вершину \(2\), а бабочка в вершине \(3\) не двигается, потому что вершина \(2\) занята. Расстояние между вершинами \(2\) и \(3\) равно \(1\).
- Ориентация ребер \(2 \rightarrow 1\) и \(2 \rightarrow 3\): бабочки в вершинах \(1\) и \(3\) не двигаются. Расстояние между вершинами \(1\) и \(3\) равно \(2\).
- Ориентация ребер \(2 \rightarrow 1\) и \(3 \rightarrow 2\): бабочка в вершине \(1\) не двигается, а бабочка из вершины \(3\) перемещается в вершину \(2\). Расстояние между вершинами \(1\) и \(2\) равно \(1\).
Таким образом, математическое ожидание счета Косии равно \(\frac {1+1+2+1} {4} = \frac {5} {4}\), что есть \(748\,683\,266\) по модулю \(998\,244\,353\).
Дерево из второго примера показано ниже. Вершины с бабочками отмечены жирным. Математическое ожидание счета Косии равно \(\frac {11} {6}\), что есть \(831\,870\,296\) по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3
1 2
2 3
|
748683266
|
|
2
|
5 3
3 4 5
1 2
1 3
2 4
2 5
|
831870296
|