Gats and the Colorful Landing

Time limit: 2000 msMemory limit: 256 MB

Gats has built a bridge consisting of $N$ stones in a row, numbered $1,2,\ldots,N$ . Each stone $i$ is assigned to one cat whose collar has color $C_i$ . Initially, every stone is empty.

There are $N$ rounds. In each round, one cat that has not yet arrived is chosen uniformly at random and jumps onto its assigned stone. Thus, every one of the $N!$ possible arrival orders is equally likely.

Suppose the cat assigned to stone $i$ has just arrived. Consider the maximal consecutive block $[L,R]$ of occupied stones containing $i$ . A colorful trio is an unordered set of three cats at positions $x$ , $y$ , and $z$ such that

L\le x<y<z\le R

and the three collar colors $C_x$ , $C_y$ , and $C_z$ are pairwise distinct.

For every colorful trio in this block, Gats catches one fish. The fish are awarded anew after every arrival, so the same trio may award another fish in a later round if it belongs to the new cat's block again.

Let $S$ be the total number of fish caught after all $N$ rounds. Compute the expected value of $S$ modulo $998244353$ .

Input

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

The second line contains $N$ integers $C_1,C_2,\ldots,C_N$ (), where is the collar color of the cat assigned to stone . Cats have the same color exactly when their integers are equal.

Output

Print one integer: the expected total number of fish, modulo $998244353$ .

More precisely, if the exact expectation is $P/Q$ in lowest terms, print

P\cdot Q^{-1}\bmod 998244353,

Samples

Sample 1

Input

2
7 8

Output

A block can never contain a trio, so Gats always catches $0$ fish.

Sample 2

Input

4
1 2 3 4

Output

499122181

Among the $24$ possible arrival orders, $12$ give a total of $4$ fish and $12$ give a total of $5$ fish. The expectation is therefore , whose required representation is .

Gats and the Colorful Landing

Input

Output

Samples

Sample 1

Sample 2

Sample 3