Дано дерево, состоящее из \(n\) вершин. Дерево — это связный неориентированный граф без циклов. Каждое ребро дерева имеет свой вес, \(w_i\).
Ваша задача — подсчитать количество различных графов, для которых одновременно выполняются четыре условия:
- В графе нет петель и кратных ребер.
- Веса на ребрах графа целые числа и не превышают \(S\).
- Граф имеет ровно одно минимальное остовное дерево.
- Минимальное остовное дерево графа является заданным деревом.
Два графа считаются различными, если их наборы рёбер различны с учётом весов рёбер.
Ответ может быть большим, выведите его по модулю \(998244353\).
Выходные данные
Для каждого теста выведите количество различных графов, удовлетворяющих условиям, по модулю \(998244353\).
Примечание
В первом примере существует единственный граф, который и является заданным деревом.
Во втором примере заданное дерево выглядит так:
Ниже изображены все возможные графы для второго примера, красным цветом выделено минимальное остовное дерево:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 5
1 2 4
4 5
1 2 2
2 3 4
3 4 3
5 6
1 2 3
1 3 2
3 4 6
3 5 1
10 200
1 2 3
2 3 33
3 4 200
1 5 132
5 6 1
5 7 29
7 8 187
7 9 20
7 10 4
|
1
8
80
650867886
|