[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$”。

输入输出格式

输入格式


第一行有三个正整数 $t, n, d$; 第二行有 $t$ 个正整数 $a_1, a_2, \ldots, 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$。 **【数据规模和约定】** 对于 $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$。