Ого, який великий коняка!

Limits: 3 sec., 512 MiB

Зеник з Марічкою планують провести екскурсію на своїй фермі для учасників обласної олімпіади з інформатики. Учасників на олімпіаді дуже багато, тому їх вирішили поділити на групи. Для кожної групи дітей екскурсію проводитимуть окремо.

На фермі Зеника й Марічки є $n$ жеребців, причому всі коні мають різні розміри.

Цьогоріч учасників олімпіади ну дуже багато, тому їх поділять аж на $n! = 1 \cdot 2 \cdot \dots \cdot n$ груп.

Для кожної групи дітей Зеник вишикує своїх $n$ коней у шеренгу. Причому порядок коней у шерензі буде різний для кожної групи дітей.

На екскурсії Марічка вестиме дітей уздовж шеренги. Коли діти підійдуть до першого коня в шерензі, вони погодують його морквою та від здивування вигукнуть хором «ого, який великий коняка!». Після цього Марічка вестиме їх далі. Вони годуватимуть кожного коня морквою по черзі в порядку шеренги. Щоразу, коли кінь, якого вони годують, має більший розмір, ніж усі коні, яких вони годували до цього, діти знов вигукуватимуть хором «ого, який великий коняка!».

Скільки разів сумарно по всіх $n!$ групах діти вигукнуть «ого, який великий коняка!»? Оскільки відповідь може бути великою, виведіть остачу від ділення відповіді на просте число $998244353$.

Input

В одному рядку задано ціле число $n$ — кількість коней.

Output

Виведіть одне ціле число — остачу від ділення відповіді на просте число $998244353$.

Constraints

$1 \le n \le 10^6$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 6 балів: $n \le 10$,

• 11 балів: $n \le 18$,

• 31 балів: $n \le 100$,

• 22 балів: $n \le 4000$,

• 27 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
2	3

Input (stdin) сopy	Output (stdout) сopy
3	11

Input (stdin) сopy	Output (stdout) сopy
47	781750049

Notes

Коли $n = 2$, на фермі є двоє жеребців — малий і великий. У цьому разі дітей поділять на $2! = 2$ групи.

• Одній групі покажуть шеренгу, де стоїть спочатку малий кінь, а потім великий. Діти в цій групі вперше здивуються, коли побачать малого коня і погодують його морквою, і вдруге здивуються коли побачать великого коня.

• Іншій групі покажуть шеренгу, де стоїть спочатку великий кінь, а потім малий. Діти здивуються один раз, коли побачать великого коня. Коли ж вони годуватимуть малого коня, його розмір уже не викликатиме в них захвату.

Загалом діти в обох групах здивуються і вигукнуть «ого, який великий коняка!» тричі.

Коли $n = 3$, на фермі є троє жеребців — малий, середній і великий. Дітей поділять на $3! = 6$ груп. Кожній групі Марічка покаже шеренгу коней в іншому порядку. Запишемо всі можливі шеренги, та підкреслимо тих коней, які викличуть здивування в дітей.

• Малий, середній, великий — три здивування.

• Малий, великий, середній — два здивування.

• Середній, малий, великий — два здивування.

• Середній, великий, малий — два здивування

• Великий, малий, середній — одне здивування.

• Великий, середній, малий — одне здивування.

Усього діти здивуються та вигукнуть «ого, який великий коняка!» одинадцять разів.

Не забудьте порахувати остачу від ділення на $998244353$.