Ini adalah soal BERPOIN (SCORED). Terdapat sepuluh subkelompok data. Setiap subkelompok akan dinilai secara independen. Menyelesaikan seluruh data dalam satu subkelompok akan memberikan nilai $0.1$ dari satu soal (Begitulah tampilannya pada papan skor, namun mungkin tertulis $10$ pada respons Kattis). Menyelesaikan seluruh data pada kesepuluh subkelompok akan memberikan nilai penuh $1$ soal. Anda dapat terus mengirimkan solusi untuk mencoba meningkatkan skor Anda.

Penalti waktu untuk soal ini akan dihitung sebagai berikut:

• Satu poin untuk setiap menit sejak awal kontes hingga pengiriman terakhir yang meningkatkan skor Anda.

• Dua puluh poin untuk setiap pengiriman sebelum pengiriman terakhir yang meningkatkan skor tersebut yang tidak meningkatkan skor Anda, dengan pengecualian kesalahan kompilasi (compiler error), yang tidak dikenakan penalti.

• Tidak ada poin penalti yang dikenakan jika skor Anda tidak pernah naik di atas nol.

Ingat lagu "The 12 Days of Christmas?"

"Pada hari pertama Natal cinta sejatiku memberiku, seekor burung puyuh di pohon pir."

Bagus sekali. Padahal aku menginginkan sebuah iPhone.

"Pada hari kedua Natal cinta sejatiku memberiku, dua ekor burung tekukur, dan seekor burung puyuh di pohon pir."

Oke, sekarang aku punya empat ekor burung: dua ekor burung tekukur dan seekor burung puyuh hari ini, serta seekor burung puyuh dari kemarin. Kucing-kucingku mulai menggila.

"Pada hari ketiga Natal cinta sejatiku memberiku, tiga ekor ayam betina Prancis, dua ekor burung tekukur, dan seekor burung puyuh di pohon pir."

Ada apa dengan semua burung ini? Hari ini bertambah enam ekor lagi, jadi sekarang aku punya sepuluh ekor, dan tidak ada tempat untuk menaruhnya (kecuali di dalam perut kucing). Berapa lama lagi cinta sejatiku bisa meneruskan hal ini?

Diberikan sebuah bilangan bulat $n$, berapa banyak hadiah yang telah aku terima setelah $n$ hari? Karena nilainya bisa sangat besar, keluarkan hasilnya dalam modulo $998\,244\,353$.

Masukan

Satu-satunya baris masukan berisi sebuah bilangan bulat $n$, yaitu jumlah hari cinta sejatiku memberiku hadiah.

Terdapat sepuluh subkelompok data, masing-masing dengan batas nilai $n$ yang berbeda:

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}$)

Keluaran

Keluarkan sebuah bilangan bulat tunggal, yaitu jumlah hadiah yang aku terima tepat setelah $n$ hari. Karena bilangan ini bisa sangat besar, keluarkan hasilnya dalam modulo $998\,244\,353$.

Contoh

Masukan 1

1

Keluaran 1

1

Masukan 2

2

Keluaran 2

4

Masukan 3

3

Keluaran 3

10