Вам дан связный неориентированный граф, в котором любые два различных простых цикла не имеют общих вершин. Так как граф может быть очень большим, он дан вам в сжатом виде: для каждого ребра вам также дано некое число \(d\), обозначающее, что на этом ребре дополнительно находится \(d\) вершин.
Требуется назначить каждой вершине и каждому ребру графа вес — целое число от \(1\) до \(3\).
Ребро графа назовём хорошим, если побитовый XOR весов смежных ему вершин не равен \(0\) и не равен весу этого ребра.
Аналогично вершину графа назовём хорошей, если побитовый XOR весов смежных ей рёбер не равен \(0\) и не равен весу этой вершины.
Вам нужно определить, сколько существует способов назначить веса вершинам и рёбрам графа, чтобы все вершины и все рёбра были хорошими. Так как ответ может быть достаточно большим, нужно вычислить остаток от деления ответа на \(998\,244\,353\).
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю \(998\,244\,353\).
Примечание
В первом тесте граф имеет вид простого цикла из \(3\) вершин. Можно показать, что есть ровно \(12\) способов назначить веса вершинам и рёбрам, чтобы все они были хорошими.
Во втором тесте граф имеет вид двух простых циклов из \(3\) вершин, соединённых ребром. Можно показать, что для такого графа нет ни одного способа расставить веса, чтобы все вершины и рёбра были хорошими.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 0
2 3 0
3 1 0
|
12
|
|
2
|
6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0
|
0
|
|
3
|
2 1
2 1 777
|
0
|
|
4
|
3 3
1 2 0
2 3 110850709
3 1 1000000000
|
179179178
|