Назовем реберно-взвешенное дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, хорошим, если вес каждого ребра равен либо $$$1$$$, либо $$$-1$$$, и для каждой вершины $$$i$$$ произведение весов ребер, смежных с вершиной $$$i$$$, равно $$$-1$$$.

Вам дано положительное целое число $$$n$$$. Всего существует $$$n^{n-2} \cdot 2^{n-1}$$$ различных$$$^\dagger$$$ реберно-взвешенных деревьев на $$$n$$$ вершинах, пронумерованных от $$$1$$$ до $$$n$$$, таких, что вес каждого ребра равен либо $$$1$$$, либо $$$-1$$$. Ваша задача — найти сумму $$$d(1,n)^\ddagger$$$ по всем таким деревьям, которые являются хорошими. Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^\dagger$$$ Два дерева называются различными, если:

• существуют две вершины такие, что в одном дереве между ними есть ребро, а в другом нет; или
• существуют две вершины такие, что в обоих деревьях между ними есть ребро, но вес этого ребра в одном дереве отличается от веса этого ребра в другом дереве.

Обратите внимание, что по формуле Кэли число деревьев с $$$n$$$ пронумерованными вершинами равно $$$n^{n-2}$$$. Так как у нас $$$n-1$$$ ребро, то для каждого дерева существует $$$2^{n-1}$$$ способ выбрать веса ребер (которые могут быть либо $$$1$$$, либо $$$-1$$$). Поэтому общее число различных реберно-взвешенных деревьев равно $$$n^{n-2} \cdot 2^{n-1}$$$.

$$$^\ddagger$$$ $$$d(u,v)$$$ обозначает сумму весов ребер на единственном простом пути от $$$u$$$ до $$$v$$$.