Þetta er STIGAGJAFA (SCORED) dæmi. Það eru tíu undirhópar af prófunargögnum. Undirhóparnir verða metnir hver í sínu lagi. Að leysa öll gögn í einum undirhópi gefur $0.1$ úr dæmi (þannig mun það líta út á stigatöflunni, en það gæti staðið $10$ í svari Kattis). Að leysa öll gögn í öllum tíu undirhópunum gefur $1$ heilt dæmi. Þú getur haldið áfram að senda inn lausnir til að reyna að bæta stigin þín.

Tímarefsing fyrir þetta dæmi er reiknuð sem hér segir:

• Eitt stig fyrir hverja mínútu frá upphafi keppni fram að síðustu innsendingu sem hækkaði stigin þín.

• Tuttugu stig fyrir hverja innsendingu á undan þessari síðustu stigahækkandi innsendingu sem hækkaði ekki stigin þín, að undanskildum þýðingarvillum (compiler errors), sem fá enga refsingu.

• Engin refsistig eru gefin ef stigin þín fara aldrei yfir núll.

Manstu eftir laginu „Jóladagarnir 12“ ("The 12 Days of Christmas")?

„Á fyrsta degi jóla gaf mín sanna ást mér akurhænu í perutré.“

Frábært. Ég vildi fá iPhone.

„Á öðrum degi jóla gaf mín sanna ást mér tvær turtildúfur og akurhænu í perutré.“

Allt í lagi, núna á ég fjóra fugla: tvær turtildúfur og akurhænu í dag, og akurhænu frá því í gær. Kettirnir mínir eru að verða vitlausir.

„Á þriðja degi jóla gaf mín sanna ást mér þrjár franskar hænur, tvær turtildúfur og akurhænu í perutré.“

Hvað er málið með alla þessa fugla? Þetta eru sex í viðbót í dag, svo núna á ég tíu stykki, og engan stað til að geyma þá (nema inni í köttunum). Hversu lengi getur mín sanna ást haldið þessu áfram?

Gefin er heiltala $n$, hversu margar gjafir hef ég fengið eftir $n$ daga? Þar sem þetta gildi getur verið stórt skaltu prenta það módúló $998\,244\,353$.

Inntak

Eina línan í inntakinu inniheldur heiltölu $n$, sem er fjöldi daga sem mín sanna ást gefur mér gjafir.

Það eru tíu undirhópar af gögnum, hver með mismunandi mörk á $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}$)

Úttak

Prentaðu eina heiltölu, sem er fjöldi gjafa sem ég fæ eftir nákvæmlega $n$ daga. Þar sem þessi tala getur verið mjög stór skaltu prenta hana módúló $998\,244\,353$.

Dæmi

Inntak 1

1

Úttak 1

1

Inntak 2

2

Úttak 2

4

Inntak 3

3

Úttak 3

10