你好，先生，我对编程非常感兴趣……但我无法解决这个问题。你能帮帮我吗？？

如果一个整数数组包含一对相邻的相等元素，则称该数组是坏的（bad）。如果一个数组不是坏的，则称它是好的（good）。

给你一个好的数组。每次你可以移除其中的一个元素，并将移除后的左右两部分拼接在一起。问有多少种依次移除所有元素的方法，使得在移除的整个过程中，数组在任何时刻都不是坏的？如果存在某一步，移除的元素在原数组中的下标不同，则认为这两种方法是不同的。

例如，从好的数组 $[2, 1, 2]$ 中移除 $1$ 后，它会变成坏的数组 $[2, 2]$；而从好的数组 $[1, 2, 3, 4, 5, 6]$ 中移除 $5$ 后，它会变成 $[1, 2, 3, 4, 6]$，并且仍然是好的。

输出在模 $998244353$ 意义下与真实答案同余的答案。形式化地，如果真实答案为 $y$，你的答案为 $x$，当 $-2^{63} \le x < 2^{63}$ 且 $x - y$ 能被 $998244353$ 整除时，你的答案将被视为正确。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示数组中元素的个数。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le n$)，表示数组的元素。

输出格式

输出一个整数，表示该问题的答案模 $998244353$ 的值。

样例

输入样例 1

3
1 2 3

输出样例 1

6

输入样例 2

4
1 2 1 2

输出样例 2

8

输入样例 3

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

输出样例 3

25660800

输入样例 4

1
1

输出样例 4

-998244352

输入样例 5

2
1 2

输出样例 5

998244355

说明

在第一个样例中，所有元素都是互不相同的，因此在任何时候都不可能得到一个坏的数组。这就是为什么有 $3! = 6$ 种移除所有元素的方法。

在第四个样例中，真实答案是 $1$，因为只有一种方法来移除唯一的元素。给出的答案 $-998244352$ 在模 $998244353$ 意义下与 $1$ 同余，因此它也是正确的。

在第五个样例中，真实答案是 $2$。

抱歉，我的英语不太好。