Dette er en POENGSATT (SCORED) oppgave. Det er ti undergrupper av testdata. Undergruppene blir vurdert uavhengig av hverandre. Å løse alle dataene i én undergruppe gir $0.1$ av en oppgave (slik vil det se ut på resultatlisten, men det kan stå $10$ i svaret fra Kattis). Å løse alle dataene i alle de ti undergruppene gir $1$ hel oppgave. Du kan fortsette å sende inn løsninger for å prøve å forbedre poengsummen din.

Tidsstraff for denne oppgaven beregnes som følger:

• Ett poeng for hvert minutt fra starten av konkurransen frem til den siste innsendingen som økte poengsummen din.

• Tjue poeng for hver innsending før denne siste poengøkende innsendingen som ikke økte poengsummen din, med unntak av kompileringsfeil, som ikke gir straff.

• Ingen straffepoeng gis dersom poengsummen din aldri stiger over null.

Husker du sangen "The 12 Days of Christmas?"

"På den første juledagen ga min sanne kjærlighet til meg, en rapphøne i et pæretre."

Flott. Jeg ønsket meg en iPhone.

"På den andre juledagen ga min sanne kjærlighet til meg, to turtelduer og en rapphøne i et pæretre."

OK, nå har jeg fire fugler: to turtelduer og en rapphøne i dag, og en rapphøne fra i går. Kattene mine holder på å bli gale.

"På den tredje juledagen ga min sanne kjærlighet til meg, tre franske høner, to turtelduer og en rapphøne i et pæretre."

Hva er greia med alle disse fuglene? Det er seks til i dag, så nå har jeg ti av dem, og ikke noe sted å gjøre av dem (bortsett fra inni kattene). Hvor lenge kan min sanne kjærlighet holde det gående?

Gitt et heltall $n$, hvor mange gaver har jeg fått etter $n$ dager? Siden denne verdien kan være stor, skal du skrive den ut modulo $998\,244\,353$.

Inndata

Den eneste linjen med inndata inneholder et heltall $n$, som er antall dager min sanne kjærlighet gir meg gaver.

Det er ti undergrupper av data, hver med ulike grenser for $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}$)

Utdata

Skriv ut ett enkelt heltall, som er antall gaver jeg mottar etter nøyaktig $n$ dager. Fordi dette tallet kan være svært stort, skal du skrive det ut modulo $998\,244\,353$.

Eksempler

Inndata 1

1

Utdata 1

1

Inndata 2

2

Utdata 2

4

Inndata 3

3

Utdata 3

10