Назовем реберно-взвешенное дерево из \(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\).
Примечание
В первом примере есть только \(1\) различное хорошее дерево. Значение \(d(1,2)\) для этого дерева равно \(-1\), что равно \(998\,244\,352\) по модулю \(998\,244\,353\).
Во втором примере значение \(d(1,1)\) для любого дерева равно \(0\), поэтому ответ равен \(0\).
В третьем примере \(16\) различных хороших деревьев. Значение \(d(1,4)\) равно:
- \(-2\) для \(2\) деревьев;
- \(-1\) для \(8\) деревьев;
- \(0\) для \(4\) деревьев;
- \(1\) для \(2\) деревьев.
Сумма \(d(1,4)\) по всем деревьям равна \(2 \cdot (-2) + 8 \cdot (-1) + 4 \cdot (0) + 2 \cdot (1) = -10\), что равно \(998\,244\,343\) по модулю \(998\,244\,353\).