F2. Покраска графа (сложная версия)
ограничение по времени на тест
5.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное различие между простой и сложной версией — ограничение на $$$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$$$.

Входные данные

В первой (и единственной) строке задано одно целое число $$$n$$$ ($$$3 \le n \le 5 \cdot 10^4$$$).

Выходные данные

Выведите одно целое число — количество способов покрасить граф, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
3
Выходные данные
6
Входные данные
4
Выходные данные
50
Входные данные
100
Выходные данные
878752271
Входные данные
1337
Выходные данные
520628749
Входные данные
42013
Выходные данные
906821221