L. Ynoalgoget
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kantipa has a string $$$S$$$ of $$$N$$$ uppercase English letters. Kantipa wants to write down a new string $$$T$$$. To do so, she first initializes $$$T$$$ as an empty string. Kantipa keeps track of a pointer on $$$S$$$ that's initially on the leftmost character. Each iteration, she does the following steps:

  1. Append a new character to the end of $$$T$$$ that's the character at the pointer in $$$S$$$.
  2. If the pointer is at the rightmost character of $$$S$$$, end the process.
  3. Else, there's a $$$50\%$$$ chance that the pointer moves to the next character to the right in $$$S$$$, or there's a $$$50\%$$$ chance that the pointer moves back to the leftmost character in $$$S$$$.

Once the process ends, Kantipa counts the number of times $$$S$$$ appears as a substring of $$$T$$$. What's the expected value of this count?

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 1\,000\,000$$$) — the length of $$$S$$$.

The second line contains a string $$$S$$$ of length $$$N$$$ consisting of uppercase English letters.

Output

It can be proven that the expected value can be expressed as a simplified fraction $$$\frac{p}{q}$$$ where $$$q$$$ is coprime with $$$998\,244\,353$$$. Print a single integer $$$Z$$$ ($$$0\leq Z \lt 998\,244\,353$$$) such that $$$Z \times q \equiv p \pmod {998\,244\,353}$$$.

Examples
Input
10
YNOALGOGET
Output
1
Input
9
GANGAGANG
Output
935854087
Note

In the first example, one possible string $$$T$$$ that can be generated is $$$\texttt{YNYYNYNOYNYNOALYNYNOALGOGET}$$$. However, no matter what happens, the number of times $$$\texttt{YNOALGOGET}$$$ appears as a substring is always $$$1$$$.

In the second example, the answer is $$$\frac{97}{16}$$$.