ด้วยจิตวิญญาณของเพลงฮิตไวรัล 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