Break The String

You are given a string $S$ consisting of lowercase English letters. Count the number of ways to break the string $S$ into $3$ strings $P, Q,$ and $R$ such that: - Concatenating $P, Q,$ and $R$ in order produces $S$, i.e., $P + Q + R = S$; - Concatenating $P$ and $R$ in order produces $Q$, i.e., $P + R = Q$. Note that $P, Q, R$ may be empty strings. ### Input - The first line of input will con