题目描述

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$ 告诉了所有学生。然后他问学生：一次游戏过程产生的颜色序列满足下列条件的概率有多大？

其中 $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。

2 3 1
1 1
1 1
2 2
3 1

1/12

3 1 2
1 1 1
5 1

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