给定 n n n 和 {ai} \{a_i\} {ai}，满足 a0≥a1≥⋯≥an−1≥0 a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0 a0≥a1≥⋯≥an−1≥0，求出在 n n n 维空间中从 (0,0,…,0) (0, 0, \ldots, 0) (0,0,…,0) 走到 (a0,a1,…,an−1) (a_0, a_1, \ldots, a_{n - 1}) (a0,a1,…,an−1)，每一步使某一维坐标增加 1 1 1 的方案中随机选出一种，满足经过的所有点 (x0,x1,…,xn−1) (x_0, x_1, \ldots, x_{n - 1}) (x0,x1,…,xn−1) 都满足 x0≥x1≥⋯≥xn−1 x_0 \geq x_1 \geq \cdots \geq x_{n - 1} x0≥x1≥⋯≥xn−1 的概率，答案模 1004535809 1004535809 1004535809 输出。

第一行一个整数 n n n，接下来一行 n n n 个整数表示 ai a_i ai。

一行一个整数表示答案。