Collar-Gap Jumps

Time limit: 2500 msMemory limit: 256 MB

A long string has $N$ equally spaced seats, numbered $1,2,\ldots,N$ from left to right. Initially, one cat sits at each seat. The cat at seat $i$ wears a collar of color $C_i$ .

The cats jump away one at a time in a uniformly random order. Equivalently, each of the $N!$ possible jump orders is equally likely.

Suppose the cat originally at seat $i$ is about to jump. Let $L$ be the seat of the nearest cat that has not yet jumped and lies to its left, and let $R$ be the corresponding nearest remaining cat to its right. Either neighbor might not exist.

The jumping cat earns points if all of the following conditions hold:

both $L$ and $R$ exist;
$C_L=C_R$ ;

When these conditions hold, the cat earns

(i-L)(R-i)

points. Otherwise, it earns $0$ points. The cat then leaves its seat permanently.

Let $S$ be the total score earned by all cats. Determine $\mathbb{E}[S]$ modulo $998244353$ .

Input

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

The second line contains $N$ integers $C_1,C_2,\ldots,C_N$ (), where is the collar color identifier of the cat initially at seat .

Output

Print one integer: the expected total score modulo $P=998244353$ .

More precisely, if $\mathbb{E}[S]=\frac{p}{q}$ in lowest terms, print

Samples

Sample 1

Input

3
1 2 1

Output

332748118

The expected total score is $\frac{1}{3}$ , whose required residue is $332748118$ .

Sample 2

Input

5
1 2 1 2 1

Output

598946613

For these five cats, the expected total score is $\frac{6}{5}$ , represented modulo as .

Collar-Gap Jumps

Input

Output

Samples

Sample 1

Sample 2

Sample 3