Gats's Mirror Yarn

Time limit: 2000 msMemory limit: 256 MB

Gats owns a piece of yarn made from $N$ physically distinct knots. Each knot has one lowercase English letter written on it. Different knots may carry the same letter.

Gats unties all the knots and then chooses uniformly at random one of the $N!$ possible orders of the $N$ distinct knots. He ties them together in that order.

A nonempty contiguous segment from position $L$ through position $R$ , where $1 \le L \le R \le N$ , is called a mirror patch if its sequence of letters reads the same from left to right and from right to left. Equivalently, for every integer $j$ satisfying $0 \le j \le R-L$ , the letters at positions $L+j$ and $R-j$ must be equal.

Gats's score is the total number of mirror patches in the resulting yarn. Segments with different endpoint pairs $(L,R)$ are counted separately, even if their letter sequences are equal.

Find the expected value of Gats's score modulo $998244353$ .

Input

The first line contains an integer $N$ $(1 \le N \le 5000)$ , the number of knots.

The second line contains a string $S$ of length $N$ . For every satisfying , the character is a lowercase English letter written on the -th knot.

Output

Let the expected score, written as a reduced fraction, be $X/Y$ . Print the unique integer $Z$ satisfying $0 \le Z < M$ and $Z \equiv X \cdot Y^{- 1} (m o d M$ where and is the multiplicative inverse of modulo .

Samples

Sample 1

Input

3
abc

Output

Because the three letters are different, every ordering has exactly three mirror patches, each consisting of one knot.

Sample 2

Input

5
aaabc

Output

299473313

The expected score is $71/10$ . Its required representation modulo $998244353$ is $299473313$ .

Gats's Mirror Yarn

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions