ברוח הלהיט הוויראלי Pen-Pineapple-Apple-Pen (PPAP) של PIKOTARO, עליכם למצוא את מספר הדרכים לבחור ארבע תתי-מחרוזות שאינן חופפות משמאל לימין במחרוזת הנתונה $S = s_1 s_2 \ldots s_n$ המורכבת אך ורק מאותיות אנגליות קטנות, כך שארבע תתי-המחרוזות מחקות את מבנה ה-PPAP האייקוני:
pen pineapple apple pen
באופן מדויק יותר, יש לבחור שמונה מספרים שלמים $i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4$ ($1 \le i_1 \le j_1 < i_2 \le j_2 < i_3 \le j_3 < i_4 \le j_4 \le n$), כך ש:
- תת-המחרוזת הראשונה ותת-המחרוזת הרביעית זהות: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. זה מייצג את ה-"pen" התואם בהתחלה ובסוף.
- תת-המחרוזת השלישית היא סיפא ממש (strict suffix) של תת-המחרוזת השנייה. כלומר, קיים מספר שלם $k_2$ ($i_2 < k_2 \le j_2$) כך שמתקיים $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. זה מבטא את הקשר בין "pineapple" ל-"apple", שבו השנייה היא סיפא ממש של הראשונה.
עליכם למצוא את מספר ה-$8$-יות הסדורות התקפות $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ המקיימות את התנאים לעיל.
קלט
ישנו מקרה בדיקה אחד בלבד בכל קובץ בדיקה.
השורה הראשונה והיחידה מכילה מחרוזת $S$ ($1 \le |S| \le 5 \times 10^3$) המציינת את המחרוזת הנתונה המורכבת אך ורק מאותיות אנגליות קטנות.
פלט
הדפיסו שורה אחת המכילה מספר שלם אחד, המציין את מספר הבחירות התקפות בסגנון PPAP. מכיוון שהתשובה עלולה להיות גדולה, הדפיסו אותה מודולו $998\,244\,353$.
דוגמאות
ppaap
1
ppapppap
16
penpineappleapplepen
1502