Cyclic Substrings

题目描述

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

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

输入格式

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 a single integer, denoting the sum modulo $998\,244\,353$.

样例 #1

样例输入 #1

5
01010

样例输出 #1

39

提示

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