I. Yacworld
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Just as you enter the beautiful planet Yacworld, the local yacs have approached you with an extremely important problem.

Yalice has a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters. She wants to determine the string's yacness, which is defined as the sum of distances over all pairs of equal substrings of $$$s$$$. Specifically, the yacness of $$$s$$$ is equal to the sum of $$$j-i$$$ over all $$$(i, j, k)$$$ where $$$1 \leq i \lt j \leq n - k + 1$$$ and $$$s_{i, i+k-1} = s_{j, j+k-1}$$$.

Please help Yalice and determine the yacness of her string!

Input

The first line of input will contain a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — denoting the length of $$$s$$$. The next line will contain a string of length $$$n$$$ consisting of lowercase English letters.

Output

Output a single integer denoting the yacness of $$$s$$$. Since this value can be large, output it modulo the prime $$$998244353$$$.

Examples
Input
6
abccab
Output
13
Input
9
aabbabcba
Output
51
Input
8
yacworld
Output
0