本住 PIKOTARO 熱門神曲《Pen-Pineapple-Apple-Pen》(PPAP)嘅精神,你需要喺一條只由細楷英文字母組成嘅字串 $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