给定长度为 $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})$，满足经过的所有点 $(x_0, x_1, \ldots, x_{n - 1})$ 都有 $x_0 \geq x_1 \geq \cdots \geq x_{n - 1}$ 的概率，随机方式是每一步均匀随机一个 $i\in [1,n]\cup \mathbb N_+$ 并令 $x_i:=x_i+1$。

$1\le n, a_i \leq 5\times 10^5$。答案对 $1004535809$ 取模。

给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。

$n \leq 5 \times 10^5, |S| = 2n - 1$。