Tämä on PISTEITETTY (SCORED) tehtävä. Testidata on jaettu kymmeneen alaryhmään. Alaryhmät arvioidaan toisistaan riippumatta. Yhden alaryhmän kaikkien testien ratkaiseminen tuottaa $0.1$ tehtäväpistettä (näin se näkyy tulostaululla, mutta Kattisin vastauksessa se voi näkyä lukuna $10$). Kaikkien kymmenen alaryhmän kaikkien testien ratkaiseminen tuottaa $1$ kokonaisen tehtävän pisteet. Voit jatkaa lähetysten tekemistä yrittääksesi parantaa pistemäärääsi.

Aikasakko tästä tehtävästä määräytyy seuraavasti:

• Yksi piste jokaiselta minuutilta kilpailun alusta viimeiseen lähetykseen, joka kasvatti pistemäärääsi.

• Kaksikymmentä pistettä jokaisesta ennen tätä viimeistä pistemäärää kasvattanutta lähetystä tehdystä lähetyksestä, joka ei kasvattanut pistemäärääsi, lukuun ottamatta käännösvirheitä, joista ei määrätä sakkoa.

• Sakkopisteitä ei määrätä lainkaan, jos pistemääräsi ei koskaan nouse nollan yläpuolelle.

Muistatko laulun "Joulun 12 päivää" ("The 12 Days of Christmas")?

"Joulun ensimmäisenä päivänä tosirakkauteni antoi minulle peltopyyn päärynäpuussa."

Mahtavaa. Minä halusin iPhonen.

"Joulun toisena päivänä tosirakkauteni antoi minulle kaksi turturikyyhkyä ja peltopyyn päärynäpuussa."

Okei, nyt minulla on neljä lintua: kaksi turturikyyhkyä ja peltopyy tänään sekä peltopyy eiliseltä. Kissani ovat tulossa hulluiksi.

"Joulun kolmantena päivänä tosirakkauteni antoi minulle kolme ranskalaista kanaa, kaksi turturikyyhkyä ja peltopyyn päärynäpuussa."

Mikä juttu näiden lintujen kanssa oikein on? Tänään tuli kuusi lisää, joten minulla on niitä nyt kymmenen, eikä mitään paikkaa mihin laittaa ne (paitsi kissojen sisään). Kuinka kauan tosirakkauteni voi jatkaa tätä?

Annettuna kokonaisluku $n$, kuinka monta lahjaa olen saanut $n$ päivän jälkeen? Koska tämä arvo voi olla suuri, tulosta se modulo $998\,244\,353$.

Syöte

Syötteen ainoa rivi sisältää kokonaisluvun $n$, joka on niiden päivien lukumäärä, joina tosirakkauteni antaa minulle lahjoja.

Testidata koostuu kymmenestä alaryhmästä, joista jokaisessa on eri rajat luvulle $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}$)

Tuloste

Tulosta yksi kokonaisluku, joka on täsmälleen $n$ päivän jälkeen saamieni lahjojen kokonaismäärä. Koska tämä luku voi olla hyvin suuri, tulosta se modulo $998\,244\,353$.

Esimerkit

Syöte 1

1

Tuloste 1

1

Syöte 2

2

Tuloste 2

4

Syöte 3

3

Tuloste 3

10