Dans l'esprit du tube viral Pen-Pineapple-Apple-Pen (PPAP) de PIKOTARO, vous devez trouver le nombre de façons de sélectionner quatre sous-chaînes disjointes de gauche à droite dans la chaîne donnée $S = s_1 s_2 \ldots s_n$, composée uniquement de lettres minuscules de l'alphabet anglais, de sorte que les quatre sous-chaînes imitent la structure emblématique de PPAP :
pen pineapple apple pen
Plus précisément, il s'agit de choisir huit entiers $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$) tels que :
- La première et la quatrième sous-chaînes sont identiques : $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Cela représente les « pen » identiques au début et à la fin.
- La troisième sous-chaîne est un suffixe strict de la deuxième sous-chaîne. Autrement dit, il existe un entier $k_2$ ($i_2 < k_2 \le j_2$) tel que $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Cela traduit la relation entre « pineapple » et « apple », où le second est un suffixe strict du premier.
Vous devez déterminer le nombre de $8$-uplets $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ valides satisfaisant les conditions ci-dessus.
Entrée
Il n'y a qu'un seul cas de test dans chaque fichier de test.
La première et unique ligne contient une chaîne $S$ ($1 \le |S| \le 5 \times 10^3$) représentant la chaîne donnée, composée uniquement de lettres minuscules de l'alphabet anglais.
Sortie
Affichez une ligne contenant un entier, indiquant le nombre de sélections valides de type PPAP. Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.
Exemples
ppaap
1
ppapppap
16
penpineappleapplepen
1502