זוהי בעיה מנוקדת (SCORED). ישנן עשר תת-קבוצות של נתונים. תת-הקבוצות ייבדקו באופן בלתי תלוי. פתרון כל הנתונים בתת-קבוצה אחת יעניק $0.1$ מבעיה (כך זה ייראה בטבלת הדירוג, אך בתגובה של Kattis עשוי להופיע $10$). פתרון כל הנתונים בכל עשר תת-הקבוצות יעניק $1$ בעיה שלמה. ניתן להמשיך ולהגיש פתרונות כדי לנסות ולשפר את הניקוד שלך.

קנס הזמן עבור בעיה זו יחושב באופן הבא:

• נקודה אחת על כל דקה מתחילת התחרות ועד להגשה האחרונה שהעלתה את הניקוד שלך.

• עשרים נקודות על כל הגשה שקדמה לאותה הגשה אחרונה שהעלתה את הניקוד ואשר לא העלתה את הניקוד שלך, למעט שגיאות קומפילציה, שעליהן לא מוטלים קנסות.

• לא מוטלות נקודות קנס אם הניקוד שלך לעולם אינו עולה מעל אפס.

זוכרים את השיר "12 ימי חג המולד" ("The 12 Days of Christmas")?

"ביום הראשון של חג המולד אהבת האמת שלי נתנה לי חוגלה על עץ אגס."

נהדר. אני רציתי iPhone.

"ביום השני של חג המולד אהבת האמת שלי נתנה לי שתי תורים, וחוגלה על עץ אגס."

אוקיי, עכשיו יש לי ארבע ציפורים: שתי תורים וחוגלה היום, וחוגלה מאתמול. החתולים שלי משתגעים.

"ביום השלישי של חג המולד אהבת האמת שלי נתנה לי שלוש תרנגולות צרפתיות, שתי תורים, וחוגלה על עץ אגס."

מה הקטע עם הציפורים? זה עוד שש היום, כך שעכשיו יש לי עשר מהן, ואין לי שום מקום לשים אותן (חוץ מאשר בתוך החתולים). כמה זמן עוד אהבת האמת שלי יכולה להמשיך בזה?

בהינתן מספר שלם $n$, כמה מתנות קיבלתי בסך הכול לאחר $n$ ימים? מכיוון שערך זה עלול להיות גדול, יש להדפיס אותו מודולו $998\,244\,353$.

קלט

השורה היחידה של הקלט מכילה מספר שלם $n$, שהוא מספר הימים שבהם אהבת האמת שלי נותנת לי מתנות.

ישנן עשר תת-קבוצות של נתונים, שלכל אחת מהן מגבלות שונות על $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}$)

פלט

הדפיסו מספר שלם יחיד, שהוא מספר המתנות שאני מקבל לאחר $n$ ימים בדיוק. מכיוון שמספר זה עלול להיות גדול מאוד, הדפיסו אותו מודולו $998\,244\,353$.

דוגמאות

קלט 1

1

פלט 1

1

קלט 2

2

פלט 2

4

קלט 3

3

פלט 3

10