Это задача С ЧАСТИЧНЫМИ БАЛЛАМИ (SCORED). Тестовые данные разделены на десять подгрупп. Подгруппы оцениваются независимо друг от друга. Прохождение всех тестов в одной подгруппе приносит $0.1$ балла за задачу (именно так это будет отображаться в таблице результатов, хотя в ответе системы Kattis может быть указано $10$). Прохождение всех тестов во всех десяти подгруппах приносит $1$ полный балл за задачу. Вы можете продолжать отправлять решения, чтобы попытаться улучшить свой результат.
Штрафное время за эту задачу начисляется следующим образом:
Одна минута штрафа за каждую минуту с начала соревнования до последней посылки, увеличившей ваш балл.
Двадцать минут штрафа за каждую посылку до этой последней увеличившей балл посылки, которая не привела к увеличению вашего балла, за исключением ошибок компиляции, за которые штраф не начисляется.
Штрафные очки не начисляются, если ваш балл так и не превысил ноль.
Помните песню «12 дней Рождества» ("The 12 Days of Christmas")?
«В первый день Рождества моя истинная любовь подарила мне куропатку на грушевом дереве».
Отлично. А я хотел iPhone.
«Во второй день Рождества моя истинная любовь подарила мне двух горлиц и куропатку на грушевом дереве».
Ладно, теперь у меня четыре птицы: две горлицы и куропатка сегодня, да ещё одна куропатка со вчерашнего дня. Мои кошки сходят с ума.
«В третий день Рождества моя истинная любовь подарила мне трёх французских кур, двух горлиц и куропатку на грушевом дереве».
Да что ж такое с этими птицами? Сегодня их ещё шесть, так что теперь у меня их десять, и мне совершенно некуда их девать (разве что внутрь кошек). Как долго моя истинная любовь сможет это продолжать?
Дано целое число $n$. Сколько всего подарков я получу за $n$ дней? Поскольку это число может быть большим, выведите его по модулю $998\,244\,353$.
Входные данные
Единственная строка входных данных содержит целое число $n$ — количество дней, в течение которых моя истинная любовь дарит мне подарки.
Имеется десять подгрупп тестов, в каждой из которых действуют свои ограничения на $n$:
($1 \le n \le 10$)
($10 < n \le 1\,000$)
($1\,000 < n \le 10^5$)
($10^5 < n \le 10^7$)
($10^7 < n \le 10^9$)
($10^9 < n \le 10^{11}$)
($10^{11} < n \le 10^{13}$)
($10^{13} < n \le 10^{15}$)
($10^{15} < n \le 10^{17}$)
($10^{17} < n \le 10^{18}$)
Выходные данные
Выведите одно целое число — общее количество подарков, которые я получу ровно через $n$ дней. Так как это число может быть очень большим, выведите его по модулю $998\,244\,353$.
Примеры
Входные данные 1
1
Выходные данные 1
1
Входные данные 2
2
Выходные данные 2
4
Входные данные 3
3
Выходные данные 3
10