Единственное различие между простой и сложной версией — ограничение на $$$n$$$.

Дан полный неориентированный граф из $$$n$$$ вершин. Полный граф — это такой граф, где между каждой парой вершин существует ровно одно ребро. Вы должны покрасить ребра этого графа в два цвета, синий и красный (каждое ребро должно быть покрашено в один из этих цветов).

Назовем множество вершин $$$S$$$ связным по красному цвету, если для каждой пары вершин $$$(v_1, v_2)$$$, такой, что $$$v_1 \in S$$$ и $$$v_2 \in S$$$, существует путь из $$$v_1$$$ в $$$v_2$$$, проходящий только по вершинам из $$$S$$$ и по красным ребрам. Аналогично, назовем множество вершин $$$S$$$ связным по синему цвету, если для каждой пары вершин $$$(v_1, v_2)$$$, такой, что $$$v_1 \in S$$$ и $$$v_2 \in S$$$, существует путь из $$$v_1$$$ в $$$v_2$$$, проходящий только по вершинам из $$$S$$$ и по синим ребрам.

Нужно раскрасить граф так, чтобы выполнялись следующие условия:

• хотя бы одно ребро красное;
• хотя бы одно ребро синее;
• для каждого множества вершин $$$S$$$, такого, что $$$|S| \ge 2$$$, $$$S$$$ связно по красному цвету или по синему цвету, но не по обоим цветам.

Посчитайте количество способов покрасить граф и выведите его по модулю $$$998244353$$$.