Maximum Scoring Palindrome Partition

Pear has a string S of length \(N\) (\(1 \le N \le 10^5\)). He wants to split the string into two non‐empty parts by choosing an index \(t\) (\(1 \le t \le N-1\)) so that the string is partitioned as \(S = P + Q\) where P = S[0..t-1] and Q = S[t..N-1] (both non‐empty).

To evaluate a partition, we define two types of palindromic substrings:

• A \(\textbf{positive palindrome}\) is defined as a palindromic substring whose length is odd. Let \(A\) be the number of distinct positive palindromic substrings contained in P.
• A \(\textbf{non-positive palindrome}\) is a palindromic substring that is not a positive palindrome – that is, it has an even length. Let \(B\) be the number of distinct non-positive palindromic substrings contained in Q.

The score of a partition is defined as \(A \times B\). Your task is to determine the maximum score over all possible splits of the string.

Note:

• When counting substrings, two substrings are considered the same if the sequence of characters is identical (i.e. they are distinct by value, not by position).
• If there is no valid palindrome of the required type in a segment, its count is considered \(0\).

Input Format

The input consists of a single line containing the string \(S\). It is guaranteed that \(1 \le |S| \le 10^5\) and \(S\) consists of lowercase English letters.

Output Format

Output a single integer, the maximum value of \(A \times B\) over all valid partitions of the string.

inputFormat

A single string \(S\).

outputFormat

A single integer representing the maximum score \(A \times B\).

sample

aba

0