Дано дерево из \(n\) вершин. Требуется выбрать \(k\) (не обязательно различных) простых путей так, чтобы все ребра дерева можно было разбить на три множества: ребра, которые не принадлежит ни одному из путей, ребра, которые принадлежат ровно одному из этих пути, и ребра, которые принадлежат всем путям, причем последнее множество должно содержать хотя бы одно ребро.
Посчитайте количество способов так выбрать \(k\) путей по модулю \(998244353\).
Пути пронумерованы, иными словами, два способа считаются различными, если существует такое \(i\) (\(1 \leq i \leq k\)) и ребро, которое присутствует в \(i\)-м пути в одном способе и отсутствует в другом.
Выходные данные
Выведите количество способов выбрать \(k\) пронумерованных не обязательно различных простых путей так, чтобы по каждому ребру дерева проходило либо ни одного пути, либо проходил один путь, либо \(k\), и пересечение всех путей было непустым.
Так как ответ может быть большим, выведите его по модулю \(998244353\).
Примечание
В первом примере подходят следующие последовательности путей：
- \(((1,2), (1,2))\),
- \(((1,2), (1,3))\),
- \(((1,3), (1,2))\),
- \(((1,3), (1,3))\),
- \(((1,3), (2,3))\),
- \(((2,3), (1,3))\),
- \(((2,3), (2,3))\).
Во втором примере \(k=1\), поэтому подходят все \(n \cdot (n - 1) / 2 = 5 \cdot 4 / 2 = 10\) путей.
В третьем примере ответ \(\geq 998244353\), поэтому он был взят по модулю \(998244353\), не забудьте про это!
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2
2 3
|
7
|
|
2
|
5 1
4 1
2 3
4 5
2 1
|
10
|
|
3
|
29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29
|
125580756
|