Це задача З ЧАСТКОВИМИ БАЛАМИ (SCORED). Тестові дані поділено на десять підгруп. Підгрупи оцінюються незалежно одна від одної. Проходження всіх тестів в одній підгрупі приносить $0.1$ бала за задачу (саме так це відображатиметься в таблиці результатів, хоча у відповіді системи Kattis може бути вказано $10$). Проходження всіх тестів у всіх десяти підгрупах приносить $1$ повний бал за задачу. Ви можете продовжувати надсилати розв'язки, щоб спробувати покращити свій результат.

Штрафний час за цю задачу нараховується таким чином:

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

• Двадцять штрафних балів за кожне подання перед цим останнім поданням, що збільшило результат, яке не призвело до збільшення вашого результату, за винятком помилок компіляції, за які штраф не нараховується.

• Штрафні бали не нараховуються, якщо ваш результат так і не перевищив нуль.

Пам'ятаєте пісню «12 днів Різдва» ("The 12 Days of Christmas")?

«Першого дня Різдва моє справжнє кохання подарувало мені куріпку на груші».

Чудово. А я хотів iPhone.

«Другого дня Різдва моє справжнє кохання подарувало мені двох горлиць і куріпку на груші».

Гаразд, тепер у мене чотири птахи: дві горлиці й куріпка сьогодні, та ще одна куріпка відучора. Мої коти божеволіють.

«Третього дня Різдва моє справжнє кохання подарувало мені трьох французьких курей, двох горлиць і куріпку на груші».

Та що ж таке з цими птахами? Сьогодні їх ще шість, тож тепер у мене їх десять, і мені зовсім нікуди їх подіти (хіба що всередину котів). Як довго моє справжнє кохання зможе це продовжувати?

Задано ціле число $n$. Скільки всього подарунків я отримаю після $n$ днів? Оскільки це значення може бути великим, виведіть його за модулем $998\,244\,353$.

Вхідні дані

Єдиний рядок вхідних даних містить ціле число $n$ — кількість днів, протягом яких моє справжнє кохання дарує мені подарунки.

Є десять підгруп даних, кожна з яких має різні обмеження на $n$:

1. ($1 \le n \le 10$)

2. ($10 < n \le 1\,000$)

3. ($1\,000 < n \le 10^5$)

4. ($10^5 < n \le 10^7$)

5. ($10^7 < n \le 10^9$)

6. ($10^9 < n \le 10^{11}$)

7. ($10^{11} < n \le 10^{13}$)

8. ($10^{13} < n \le 10^{15}$)

9. ($10^{15} < n \le 10^{17}$)

10. ($10^{17} < n \le 10^{18}$)

Вихідні дані

Виведіть одне ціле число — кількість подарунків, які я отримаю рівно через $n$ днів. Оскільки це число може бути дуже великим, виведіть його за модулем $998\,244\,353$.

Приклади

Вхідні дані 1

1

Вихідні дані 1

1

Вхідні дані 2

2

Вихідні дані 2

4

Вхідні дані 3

3

Вихідні дані 3

10