Mr. Ham is interested in strings, especially palindromic strings. Today, he finds a string $$$s$$$ of length $$$n$$$.

For the string $$$s$$$ of length $$$n$$$, he defines its cyclic substring from the $$$i$$$-th character to the $$$j$$$-th character ($$$1\leq i,j\leq n$$$) as follows:

• If $$$i \leq j$$$, the cyclic substring is the substring of $$$s$$$ from the $$$i$$$-th character to the $$$j$$$-th character. He denotes it as $$$s[i..j]$$$.
• If $$$i \gt j$$$, the cyclic substring is $$$s[i..n] + s[1..j]$$$, where $$$+$$$ denotes the concatenation of two strings. He also denotes it as $$$s[i..j]$$$.

For example, if $$$s = \texttt{12345}$$$, then $$$s[2..4] = \texttt{234}$$$, $$$s[4..2] = \texttt{4512}$$$, and $$$s[3..3] = \texttt{3}$$$.

A string $$$t$$$ is palindromic if $$$t[i]=t[n-i+1]$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$. For example, $$$\texttt{1221}$$$ is palindromic, while $$$\texttt{123}$$$ is not.

Given the string $$$s$$$, there will be many cyclic substrings of $$$s$$$ which are palindromic. Denote $$$P$$$ as the set of all distinct cyclic substrings of $$$s$$$ which are palindromic, $$$f(t)(t \in P)$$$ as the number of times $$$t$$$ appears in $$$s$$$ as a cyclic substring, and $$$g(t)(t \in P)$$$ as the length of $$$t$$$. Mr. Ham wants you to compute $$$$$$\sum_{t \in P} f(t)^2 \times g(t)$$$$$$

The answer may be very large, so you only need to output the answer modulo $$$998\,244\,353$$$.