Collars on the Waking String

Time limit: 3000 msMemory limit: 256 MB

There are $N$ cats sitting at fixed positions $1,2,\ldots,N$ along a taut string. The cat at position $i$ wears a collar of color $C_i$ .

The cats wake up one at a time. Their wake order is chosen uniformly at random from all $N!$ permutations. Once a cat wakes, it remains awake.

When the cat at position $i$ wakes, it looks for cats that woke earlier:

If there is no previously awakened cat to its left or no previously awakened cat to its right, it earns no purr.
Otherwise, let $L$ be the largest previously awakened position smaller than $i$ , and let $R$ be the smallest previously awakened position larger than $i$ . The cat earns one purr if both $C_L=C_R$ and hold.

Let $X$ be the total number of purrs earned after every cat has awakened. Compute $\mathbb{E}[X]$ modulo $998244353$ .

Input

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

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

Print the expected value of $X$ modulo $P=998244353$ .

More precisely, if $\mathbb{E}[X]=a/b$ for integers $a$ and with , print

Input

1
7

Output

With only one cat, no purr can be earned, so the expected total is $0$ .

Input

3
1 2 1

Output

332748118

The expected number of purrs is $1/3$ , represented modulo $998244353$ as $332748118$ .

Input

4
1 2 1 1

Output

915057324

For this arrangement, the expected number of purrs is $5/12$ .