Тима и Батыр играют серию матчей в игре UFC. В игре присутствует $$$n$$$ бойцов, которые пронумерованы в порядке своей силы от $$$1$$$ (самый слабый) до $$$n$$$ (самый сильный).
Планируется провести $$$n$$$ матчей таким образом, чтобы каждый игрок сыграл ровно один раз с каждым бойцом. Перед началом серии Тима и Батыр выбирают порядок, в котором они будут играть своими бойцами.
В каждом матче победитель определяется по силе выбранного игроком бойца. Если оба игрока выбирают одного и того же бойца, то матч считается ничьей, и Тима объявляется победителем благодаря своему возрасту.
Если в какой-то момент серии Батыр выигрывает больше матчей, чем Тима, он объявляет себя более сильным игроком и уходит домой. Однако, если все $$$n$$$ матчей сыграны, и Батыр не ушел домой, то он признает силу Тимы.
Вам, как самому верному фанату Тимы, стало интересно: сколько есть способов выбрать порядок бойцов для игроков так, чтобы Тима утер нос Батыру? Так как ответ может быть очень большим, вычислите его по модулю $$$998\, 244\, 353$$$.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество бойцов и, соответственно, матчей.
Выведите одно число — количество способов по модулю $$$998\, 244\, 353$$$.
1
1
2
3
3
22
4
310
Во втором примере, всего существуют $$$4$$$ возможных способов выбрать порядок бойцов. Единственный из них, где Батыр выигрывает, это способ, где Батыр выбирает порядок бойцов $$$(2, 1)$$$, а Тима выбирает порядок бойцов $$$(1, 2)$$$. В данном случае Батыр выигрывает первый матч, сразу объявляет себя победителем и уходит домой.
В четвертом примере, всего существуют $$$576$$$ возможных способов выбрать порядок бойцов. Если Батыр выберет порядок бойцов $$$(1, 4, 3, 2)$$$ и Тима выберет порядок бойцов $$$(1, 3, 2, 4)$$$, то серия будет происходить следующим образом:
| SDU Open 2023 |
|---|
| Закончено |
