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

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

样例输出 1

753401857

样例输入 2

10
10 10 10 10 10 10 10 10 10 10

样例输出 2

187948134

样例输入 3

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

样例输出 3

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