В новом регионе Сэм обнаружил $$$n + 1$$$ городов, соединенных двусторонними дорогами. Причем, $$$n$$$ из этих городов расположены на окружности, а один город является столицей и расположен в центре. Пронумеруем города на окружности от $$$1$$$ до $$$n$$$ в порядке обхода, и назначим столице номер $$$n + 1$$$. Каждая дорога либо соединяет столицу с городом на окружности, либо соединяет два соседних города на окружности. Иными словами, дорога соединяет города $$$(n + 1)$$$ и $$$v$$$ или города $$$v$$$ и $$$(v \bmod n + 1)$$$, где $$$v \in [1, n]$$$.

Каждая дорога контролируется одной из конкурирующих банд: либо бандой Уайта, либо бандой Блэка. Сэм хочет выбрать и обезопасить минимальное количество дорог, по которым можно было бы добраться от любого города до любого другого. Другими словами, Сэм хочет выбрать остовное дерево в графе городов. Можно доказать, что любое остовное дерево будет содержать ровно $$$n$$$ дорог.

Для того, чтобы обезопасить дорогу, нужно договориться с главарём банды, контролирующей эту дорогу. Сэм ещё не знает, кто из Уайта и Блэка окажется сговорчивее, поэтому попросил вас для каждого целого $$$k \in [0, n]$$$ посчитать количество способов выбрать остовное дерево, чтобы ровно $$$k$$$ из выбранных дорог контролировались бандой Уайта, а $$$n - k$$$ оставшихся дорог — бандой Блэка. Так как ответы могут быть большими, посчитайте их по модулю $$$998\,244\,353$$$.