피코타로(PIKOTARO)의 인기 히트곡 펜-파인애플-애플-펜(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)입니다. 즉, $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$를 만족하는 정수 $k_2$ ($i_2 < k_2 \le j_2$)가 존재합니다. 이는 후자가 전자의 진접미사인 "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