انطلاقاً من روح الأغنية الشهيرة 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