题目描述

给定 $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

10
10 10 10 10 10 10 10 10 10 10

187948134

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

608067952

数据范围与提示