344. [NOI 2006]神奇口袋

【题目描述】

$Pòlya$ 获得了一个奇妙的口袋，上面写着人类难以理解的符号。$Pòlya$ 看得入了迷，冥思苦想，发现了一个神奇的模型（被后人称为 $Pòlya$ 模型)。为了生动地讲授这个神奇的模型，他带着学生们做了一个虚拟游戏：

游戏开始时，袋中装入 $a_1$ 个颜色为 $1$ 的球，$a_2$ 个颜色为 $2$ 的球，…，$a_t$ 个颜色为 $t$ 的球，其中 $a_i ∈ Z^+$  $(1 ≤ i ≤ t)$ 。

游戏开始后，每次严格进行如下的操作：

从袋中随机的抽出一个小球（袋中所有小球被抽中的概率相等），$Pòlya$ 独自观察这个小球的颜色后将其放回，然后再把 $d$ 个与其颜色相同的小球放到口袋中。

设 $c_i$ 表示第 $i$ 次抽出的小球的颜色 $(1 ≤ c_i ≤ t)$ ，一个游戏过程将会产生一个颜色序列 $(c_1,c_2,…,c_n,…)$。

$Pòlya$ 把游戏开始时 $t$ 种颜色的小球每一种的个数 $a_1,a_2,…,a_t$ 告诉了所有学生。然后他问学生：一次游戏过程产生的颜色序列满足下列条件的概率有多大？

$c_{x_1} = y_1, c_{x_2} = y_2, \dots, c_{x_i} = y_i, \dots, c_{x_n} = y_n$

其中 $0 < x_1 < x_2 < \dots < x_n$，$1 ≤ y_i ≤ t$ 。换句话说，已知 $(t,n,d,a_1,a_2,…,a_t,x_1,y_1,x_2,y_2,...,x_n,y_n)$，你要回答有多大的可能性会发生下面的事件：“对所有 $k, 1 ≤ k ≤ n$ ，第 $x_k$ 次抽出的球的颜色为 $y_k$”。

【输入格式】

第一行有三个正整数 $t，n，d$； 第二行有 $t$ 个正整数 $a_1,a_2,…,a_t$，表示游戏开始时口袋里 $t$ 种颜色的球，每种球的个数。

以下 $n$ 行，每行有两个正整数 $x_i,y_i$，表示第 $x_i$ 次抽出颜色为的 $y_i$ 球。

【输出格式】

要求用分数形式输出（显然此概率为有理数）。输出文件包含一行，格式为：

分子/分母。同时要求输出最简形式（分子分母互质）。特别的，概率为 $0$ 应输出 $0/1$，概率为 $1$ 应输出 $1/1$。

【输入输出样例】

样例 $1$ 输入:

2 3 1
1 1
1 1
2 2
3 1

样例 $1$ 输出:

1/12

样例 $2$ 输入：

3 1 2
1 1 1
5 1

样例 $2$ 输出：

1/3

【样例 $1$ 说明】

初始时，两种颜色球数分别为 $(1, 1)$，取出色号为 $1$ 的球的概率为 $1/2$；第二次取球之前，两种颜色球数分别为 $(2, 1)$，取出色号为 $2$ 的球的概率为 $1/3$；第三次取球之前，两种颜色球数分别为 $(2, 2)$，取出色号为 $1$ 的球的概率为 $1/2$，所以三次取球的总概率为 $1/12$。

【评分方法】

本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

【数据范围】

$1 ≤ t,n ≤ 1000, 1 ≤ a_k ,d ≤ 10, 1 ≤ x_1 < x_2 < … < x_n ≤ 10000, 1 ≤ y_k ≤ t$。