C. Cyclic Substrings
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$.

Input

The first line contains a number $$$n$$$ ($$$1 \leq n \leq 3\times 10^6$$$), the length of the string $$$s$$$.

The second line contains a string $$$s$$$ of length $$$n$$$. Each character of $$$s$$$ is a digit.

Output

Output a single integer, denoting the sum modulo $$$998\,244\,353$$$.

Examples
Input
5
01010
Output
39
Input
8
66776677
Output
192
Note

In the sample, the palindromic cyclic substrings of $$$s$$$ are:

  • $$$s[1..1] = s[3..3] = s[5..5] = \texttt{0}$$$.
  • $$$s[2..2] = s[4..4] = \texttt{1}$$$.
  • $$$s[5..1] = \texttt{00}$$$.
  • $$$s[1..3] = s[3..5] = \texttt{010}$$$.
  • $$$s[2..4] = \texttt{101}$$$.
  • $$$s[4..2] = \texttt{1001}$$$.
  • $$$s[1..5] = \texttt{01010}$$$.

The answer is $$$3^2 \times 1 + 2^2 \times 1 + 1^2 \times 2 + 2^2 \times 3 + 1^2 \times 3 + 1^2 \times 4 + 1^2 \times 5 = 39$$$.