题目描述

来自 JZYZ 的小伙到了一盒 JZYZ 牌有 n 块的巧克力，他非常开心，并且准备品尝这盒美味。

每块巧克力有自己的味道 $a_i$，我们用数字区分这些不同的味道。（同一种味道的巧克力可能会在这盒巧克力中出现多次）

小梅次都可以任选一块巧克力吃掉，吃掉后，相邻的两块会挨在一起，例如：原先巧克力为 $[1,2,3,1]$，吃掉味道记为 2 的这一块后序列会变为 $[1,3,1]$。

并且，小希望，在自己开始吃巧克力之后，任意一个时候，没有任何两块相邻巧克力的口味是相同的。

求小吃巧克力的方案数，两种方案不同当且仅当某一次吃掉的巧克力块，对应在原整盒巧克力的位置不同。例如：$[3,1,3]$ 这盒巧克力，吃的顺序为 $132=312$ 与 $123=321$ 被认为是四种不同的方案。

而且，Lift was like a box of chocolates, you never know what you're gonna get，所以不保证原整盒巧克力中，两两相邻的巧克力彼此味道不同。

（由于方案数可能会很多，所以答案对998244353取模）

输入格式

第一行一个数 $n$ 代表巧克力的块数
第二行 $n$ 个数，第 $i$ 个数 $a_i$ 代表第 $i$ 块巧克力的口味。

输出格式

一行一个数 $ans$ 代表方案数对998244353取模的值。

样例

输入样例1

3
1 2 3

输出样例1

6

输入样例2

2
1 1

输出样例2

2

输入样例3

3
1 1 1

输出样例3

0

输入样例4

12
1 2 3 1 2 3 1 2 3 1 2 3

输出样例4

25660800

数据范围与提示

对于100%的数据，$1 \leq n \leq 500$, $1 \leq a_i \leq n$

子任务编号	$n \leq$	$a_i \leq$	特殊性质	分数
1	10	$n$	无	20
2	20
3	500	2
4		$n$	$a_i$任意相邻两个位置互不相同
5			无