G. Подсчет графов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево, состоящее из $$$n$$$ вершин. Дерево — это связный неориентированный граф без циклов. Каждое ребро дерева имеет свой вес, $$$w_i$$$.

Ваша задача — подсчитать количество различных графов, для которых одновременно выполняются четыре условия:

  1. В графе нет петель и кратных ребер.
  2. Веса на ребрах графа целые числа и не превышают $$$S$$$.
  3. Граф имеет ровно одно минимальное остовное дерево.
  4. Минимальное остовное дерево графа является заданным деревом.

Два графа считаются различными, если их наборы рёбер различны с учётом весов рёбер.

Ответ может быть большим, выведите его по модулю $$$998244353$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$S$$$ ($$$2 \le n \le 2 \cdot 10^5, 1\le S\le 10^9$$$) — количество вершин и верхняя граница весов.

Затем следуют $$$n-1$$$ строк, описывающих дерево, $$$i$$$-я строка содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1\le u_i,v_i\le n, u_i \ne v_i, 1\le w_i\le S$$$) — ребро в дереве с весом $$$w_i$$$.

Гарантируется, что сумма $$$n$$$ для всех тестов не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого теста выведите количество различных графов, удовлетворяющих условиям, по модулю $$$998244353$$$.

Пример
Входные данные
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
Примечание

В первом примере существует единственный граф, который и является заданным деревом.

Во втором примере заданное дерево выглядит так:

Ниже изображены все возможные графы для второго примера, красным цветом выделено минимальное остовное дерево: