题目描述

给定 $n$ 和序列 $\{a_i\}$，满足

$$a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0$$

求出在 $n$ 维空间中从 $(0, 0, \ldots, 0)$ 走到 $(a_0, a_1, \ldots, a_{n - 1})$，每一步使某一维坐标增加 $1$ 的方案中随机选出一种，满足经过的所有点 $(x_0, x_1, \ldots, x_{n - 1})$ 都满足

$$x_0 \geq x_1 \geq \cdots \geq x_{n - 1}$$

的概率，答案对 $1004535809$ 取模输出。

---

输入格式

第一行一个整数 $n$。
接下来一行 $n$ 个整数表示 $a_i$。

---

输出格式

一行一个整数表示答案。

---

样例

样例 1

输入

2
3 3

输出

753401857

样例 2

输入

10
10 10 10 10 10 10 10 10 10 10

输出

187948134

样例 3

输入

20
19 19 17 15 14 13 13 11 10 10 9 7 6 5 5 4 2 1 1 0

输出

608067952

---

数据范围与提示

测试点	$n$	$a_i$	特殊限制
1	4	$\leq 4$
2	6	$\leq 6$
3	8	$\leq 8$
4	10	$\leq 10$
5	2	$\leq 500000$	所有 $a_i$ 相等
6
7	3		所有 $a_i$ 相等
8
9	3000		所有 $a_i$ 相等
10
11	500000		所有 $a_i$ 相等
12			$a_i$ 为等差数列
13		$\leq 50$
14		$\leq 3000$
15	30000	$\leq 30000$
16	50000	$\leq 50000$
17	100000	$\leq 100000$
18	200000	$\leq 200000$
19	300000	$\leq 300000$
20	500000	$\leq 500000$