A6667. 「雅礼集训 2017 Day11」PATH

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

一行一个整数表示答案。

|测试点| $ 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| $ 2 $ | $ \leq 500000 $ | |
|7| $ 3 $ | $ \leq 500000 $ | 所有 $ a_i $ 相等 |
|8| $ 3 $ | $ \leq 500000 $ | |
|9| $ 3000 $ | $ \leq 500000 $ | 所有 $ a_i $ 相等 |
|10| $ 3000 $ | $ \leq 500000 $ | |
|11| $ 500000 $ | $ \leq 500000 $ | 所有 $ a_i $ 相等 |
|12| $ 500000 $ | $ \leq 500000 $ | $ a_i $ 为等差数列 |
|13| $ 500000 $ | $ \leq 50 $ | |
|14| $ 500000 $ | $ \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 $ | |