本著 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