Пусть \(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\) (простое число).
Примечание
В первом примере есть \(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\).