Дан неориентированный граф из \(n\) вершин и \(n\) ребер, при этом \(n\) делится на \(6\). У каждого ребра есть вес — положительное целое число.
Структура графа имеет следующий вид: граф разделен на \(\frac{n}{3}\) троек вершин, в первую тройку входят вершины \(1, 2, 3\), во вторую — \(4, 5, 6\), и так далее. Каждая пара вершин из одной и той же тройки соединена ребром. Ни одно ребро не соединяет две вершины из разных троек.
Вершины этого графа надо раскрасить в два цвета, красный и синий. Каждая вершина должна быть покрашена в один из цветов; ровно \(\frac{n}{2}\) вершин должно быть покрашено в красный, и ровно \(\frac{n}{2}\) — в синий. Раскраски, отвечающие этим условиям, будем называть валидными.
Вес раскраски — это суммарный вес всех ребер, соединяющих вершины разных цветов.
Пусть \(W\) — максимальный вес валидной раскраски. Посчитайте количество валидных раскрасок с весом \(W\) и выведите результат по модулю \(998244353\).
Примечание
На картинке изображен граф из первого теста.
Максимальный вес валидной раскраски этого графа равен \(31\).