P4204 [NOI2006] 神奇口袋

Pòlya 获得了一个奇妙的口袋，上面写着人类难以理解的符号。Pòlya 看得入了迷，冥思苦想，发现了一个神奇的模型（被后人称为 Pòlya 模型)。为了生动地讲授这个神奇的模型，他带着学生们做了一个虚拟游戏：游戏开始时，袋中装入 $a_1$ 个颜色为 $1$ 的球，$a_2$ 个颜色为 $2$ 的球，……，$a_t$ 个颜色为 $t$ 的球，其中 $a_i \in \mathbb Z^+$（$1 \le i \le t$）。 游戏开始后，每次严格进行如下的操作： 从袋中随机的抽出一个小球（袋中所有小球被抽中的概率相等），Pòlya 独自观察这个小球的颜色后将其放回，然后再把 $d$ 个与其颜色相同的小球放到口袋中。 设 $c_i$ 表示第 $i$ 次抽出的小球的颜色（$1 \le C_i \le t$），一个游戏过程将会产生一个颜色序列（$c_1, c_2, \ldots, c_n, \ldots$）。Pòlya 把游戏开始时 $t$ 种颜色的小球每一种的个数 $a_1, a_2, \ldots, a_t$ 告诉了所有学生。然后他问学生：一次游戏过程产生的颜色序列满足下列条件的概率有多大？ $$c_{x_1}=y_1, c_{x_2}=y_2, \ldots, c_{x_n}=y_n$$ 其中 $0 < x_1 < x_2 < \cdots < x_n$，$1 \le y_i \le t$。换句话说，已知 $(t, n, d, a_1, a_2, \ldots, a_t, x_1, y_1, x_2, y_2, \ldots, x_n, y_n)$，你要回答有多大的可能性会发生下面的事件：“对所有 $k$（$1 \le k \le n$），第 $x_k$ 次抽出的球的颜色为 $y_k$”。

无

无

**【样例解释 #1】** 初始时，两种颜色球数分别为 $(1, 1)$，取出色号为 $1$ 的球的概率为 $1/2$；第二次取球之前，两种颜色球数分别为 $(2, 1)$，取出色号为 $2$ 的球的概率为 $1/3$；第三次取球之前，两种颜色球数分别为 $(2, 2)$，取出色号为 $1$ 的球的概率为 $1/2$，所以三次取球的总概率为 $1/12$。 **【数据规模和约定】** 对于 $100 \%$ 的数据，$1 \le t, n \le 1000$，$1 \le a_k, d \le 10$，$1 \le x_1 < x_2 < \cdots < x_n \le 10000$，$1 \le y_k \le t$。