Дороги после землетрясения
В горах Джалал-Абадской области n сёл соединены m дорогами (между двумя сёлами может быть несколько дорог). После землетрясения дорога i осталась проезжей с вероятностью p[i] / 100, независимо от других дорог.
Спасатели хотят знать, с какой вероятностью из любого села всё ещё можно добраться до любого другого по проезжим дорогам.
Ответ — рациональное число P / Q; выведите P · Q⁻¹ по модулю 998244353.
Входные данные
В первой строке — два целых числа n и m (1 ≤ n ≤ 16, 0 ≤ m ≤ 200). В каждой из следующих m строк — три целых числа u v p (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ p ≤ 100).
Выходные данные
Выведите вероятность того, что все сёла связаны, по модулю 998244353.
Пример 1
Вход:
3 3
1 2 50
2 3 50
1 3 50
Выход:
499122177
Пояснение
Треугольник из дорог с вероятностями 1/2: сёла связаны, если уцелели хотя бы две дороги из трёх, — это 4 случая из 8, вероятность 1/2 (по модулю 499122177).
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 12, ещё в 10 % тестов n ≤ 10.
Комментарии