该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6051.zip](file://AdditionalFile6051.zip?type=additional_file)

#6051. 「雅礼集训 2017 Day11」PATH

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

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

数据范围与提示