让我们看看你处理计数问题的能力如何。问题如下。我们称 $k$ 个集合 $S_1, S_2, \dots, S_k$ 为集合 $\{1, 2, \dots, N\}$ 的一个划分，如果：

• $\bigcup_{i=1}^k S_i = \{1, 2, \dots, N\}$ 且
• $S_i \cap S_j = \varnothing$，对于所有 $1 \le i < j \le k$。

给定一个长度为 $N$ 的正整数数组，记为 $a_1, a_2, \dots, a_N$。对于集合 $\{1, 2, \dots, N\}$ 的任意划分 $S_1, S_2, \dots, S_k$，我们定义该划分的价值为：

$$\sum_{i=1}^k f(S_i)$$

其中

$$f(S) = \binom{\max_{i \in S} a_i}{\min_{i \in S} a_i}$$

这里 $\binom{n}{m}$ 表示二项式系数：从 $n$ 个不同元素中选择 $m$ 个元素的方法数。

你需要输出 $\{1, 2, \dots, N\}$ 所有不同划分的价值总和，对 $998\,244\,353$ 取模。如果存在两个整数 $i$ 和 $j$，使得它们在某一个划分中属于同一个集合，而在另一个划分中属于不同的集合，则这两个划分被认为是不同的。

输入格式

第一行包含一个整数 $N$，表示数组的长度 $(1 \le N \le 10^5)$。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$：数组的内容 $(1 \le a_i \le 1000)$。

输出格式

输出一个整数，表示所有不同划分的价值总和，对 $998\,244\,353$ 取模。

样例

样例输入 1

3
1 2 3

样例输出 1

17

样例输入 2

6
1 1 4 5 1 4

样例输出 2

1716