D. Новый год и конкатенация перестановок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$n$$$ — целое число. Рассмотрим все перестановки целых чисел от $$$1$$$ до $$$n$$$ в лексикографическом порядке. Объедините их в одну большую последовательность $$$p$$$. Например, если $$$n = 3$$$, то $$$p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$. Длина этой последовательности будет $$$n \cdot n!$$$.

Пусть $$$1 \leq i \leq j \leq n \cdot n!$$$ — пара индексов. Мы называем последовательность $$$(p_i, p_{i+1}, \dots, p_{j-1}, p_j)$$$ подотрезком $$$p$$$. Его длина определяется как количество элементов, то есть $$$j - i + 1$$$. Его сумма определяется как сумма всех его элементов, то есть $$$\sum_{k=i}^j p_k$$$.

Дано $$$n$$$. Найдите количество подотрезков $$$p$$$ длины $$$n$$$, имеющих сумму $$$\frac{n(n+1)}{2}$$$. Поскольку это число может быть большим, выведите его по модулю $$$998244353$$$ (простое число).

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

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$), которое описано в условии задачи.

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

Выведите одно число — количество подотрезков длины $$$n$$$, в которых сумма равна $$$\frac{n(n+1)}{2}$$$, по модулю $$$998244353$$$.

Примеры
Входные данные
3
Выходные данные
9
Входные данные
4
Выходные данные
56
Входные данные
10
Выходные данные
30052700
Примечание

В первом примере есть $$$16$$$ подотрезков длины $$$3$$$. В порядке появления это:

$$$[1, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 1]$$$.

Их суммы равны $$$6$$$, $$$6$$$, $$$7$$$, $$$6$$$, $$$7$$$, $$$5$$$, $$$6$$$, $$$6$$$, $$$8$$$, $$$6$$$, $$$7$$$, $$$5$$$, $$$6$$$, $$$6$$$, $$$7$$$, $$$6$$$. Поскольку $$$\frac{n(n+1)}{2} = 6$$$, то ответ — $$$9$$$.