题目描述
给定 $ n $ 和 $ {a_i} $，满足 $ a_0 \geq a1 \geq \cdots \geq a{n - 1} \geq 0 $，求出在 $ n $ 维空间中从 $ (0, 0, \ldots, 0) $ 走到 $ (a_0, a1, \ldots, a{n - 1}) $，每一步使某一维坐标增加 $ 1 $ 的方案中随机选出一种，满足经过的所有点 $ (x_0, x1, \ldots, x{n - 1}) $ 都满足 $ x_0 \geq x1 \geq \cdots \geq x{n - 1} $ 的概率，答案模 $ 1004535809 $ 输出。
输入格式
第一行一个整数 $ n $，接下来一行 $ n $ 个整数表示 $ a_i $。
输出格式
一行一个整数表示答案。
样例 1
input
2
3 3output
753401857
样例 2
input
10
10 10 10 10 10 10 10 10 10 10output
187948134
样例 3
input
20
19 19 17 15 14 13 13 11 10 10 9 7 6 5 5 4 2 1 1 0output
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 | $ 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 $ |