To zadanie jest PUNKTOWANE (SCORED). Dane testowe podzielono na dziesięć podgrup. Podgrupy będą oceniane niezależnie. Rozwiązanie wszystkich testów w jednej podgrupie daje $0.1$ punktu za zadanie (tak będzie to wyglądać w tabeli wyników, natomiast w odpowiedzi systemu Kattis może pojawić się wartość $10$). Rozwiązanie wszystkich testów we wszystkich dziesięciu podgrupach daje pełny $1$ punkt za zadanie. Możesz przesyłać kolejne zgłoszenia, aby spróbować poprawić swój wynik.

Kara czasowa za to zadanie będzie naliczana w następujący sposób:

• Jeden punkt karny za każdą minutę od początku zawodów do ostatniego zgłoszenia, które zwiększyło Twój wynik.

• Dwadzieścia punktów karnych za każde zgłoszenie wysłane przed tym ostatnim zgłoszeniem zwiększającym wynik, które nie zwiększyło Twojego wyniku, z wyjątkiem błędów kompilacji, za które kara nie jest naliczana.

• Punkty karne nie są naliczane, jeśli Twój wynik nigdy nie wzrośnie powyżej zera.

Pamiętasz piosenkę „12 dni Świąt” ("The 12 Days of Christmas")?

„Pierwszego dnia Świąt moja prawdziwa miłość dała mi kuropatwę na gruszy.”

Świetnie. Chciałem iPhone'a.

„Drugiego dnia Świąt moja prawdziwa miłość dała mi dwie turkawki i kuropatwę na gruszy.”

OK, teraz mam cztery ptaki: dwie turkawki i kuropatwę z dzisiaj oraz kuropatwę z wczoraj. Moje koty dostają szału.

„Trzeciego dnia Świąt moja prawdziwa miłość dała mi trzy francuskie kury, dwie turkawki i kuropatwę na gruszy.”

O co chodzi z tymi ptakami? Dzisiaj doszło kolejne sześć, więc mam ich już dziesięć i żadnego miejsca, żeby je trzymać (chyba że wewnątrz kotów). Jak długo moja prawdziwa miłość może to jeszcze ciągnąć?

Mając daną liczbę całkowitą $n$, oblicz, ile prezentów otrzymałem łącznie po $n$ dniach. Ponieważ wynik może być duży, wypisz go modulo $998\,244\,353$.

Wejście

Jedyny wiersz wejścia zawiera liczbę całkowitą $n$, oznaczającą liczbę dni, przez które moja prawdziwa miłość daje mi prezenty.

Istnieje dziesięć podgrup danych, z których każda ma inne ograniczenie na $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}$)

Wyjście

Wypisz jedną liczbę całkowitą — liczbę prezentów, które otrzymam po dokładnie $n$ dniach. Ponieważ liczba ta może być bardzo duża, wypisz ją modulo $998\,244\,353$.

Przykład

Wejście 1

1

Wyjście 1

1

Wejście 2

2

Wyjście 2

4

Wejście 3

3

Wyjście 3

10