National Olympiad in Informatics, China, 2006

Pòlya received a magical bag with symbols written on it that are difficult for humans to understand. Pòlya is in awe of the symbols. As he is painstakingly trying to contemplate their meaning, he discovered a magical model (known to later generations as the Pòlya model). To make the teaching of his model more vivid and interesting, he created a game for his students to play.

At the start of the game, the bag contains $a_1$ balls of color $1$, $a_2$ balls of color $2$, …, $a_t$ balls of color $t$, where $a_i\in {\mathbb{Z}}^{+}$ $(1\le i\le t)$.

After the game has started, the following actions are strictly followed at each step: Randomly draw a ball from the bag (there is equal probability for drawing any ball). After Pòlya individually looks at the color of the ball, he places the ball back into the bag, and then places $d$ balls of this color into the bag.

Let $c_i$ represent the color of the ball drawn during the $i$-th step $(1\le c_i\le t)$, then the process of the game will yield a color sequence $(c_1,c_2,\dots ,c_n,\dots )$.

Regarding the $t$ types of colored balls at the start of the game, Pòlya has told all of the students the amount $a_1,a_2,\dots ,a_t$ of each type. Then he asks his students: What is the probability of the color sequence from a single game satisfying the following conditions?

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

where $0<x_1<x_2<\cdots <x_n$ and $1\le y_i\le t$. In other words, given $(t,n,d,a_1,a_2,\dots ,a_t,x_1,y_1,x_2,y_2,\dots ,x_n,y_n)$, you must determine the probability of the following event: "for all $k$, $1\le k\le n$, the ball drawn in the $x_k$-th draw has color $y_k$."

Input Specification

The first line contains three positive integer $t,n$ $(1\le t,n\le 1000)$, and $d$ $(1\le d\le 10)$.
The second line contains $t$ integers $a_1,a_2,\dots ,a_t$ $(1\le a_k\le 10)$ representing the amount of each type of the $t$ types of colored balls at the start of the game.
For the next $n$ lines, each line contains a pair of positive integers $x_i,y_i$ $(1\le x_1<x_2<\cdots <x_n\le 10000;1\le y_k\le t)$, indicating that in step $x_i$, a ball of color $y_i$ is drawn.

Output Specification

Determine the answer in fraction form (it is clear that this probability is a rational number). Output a single line in the format: numerator/denominator. At the same time, output a reduced fraction (where the numerator and denominator are relatively prime). For the probability of $0$, output 0/1. For the probability of $1$, output 1/1.

Sample Input 1

2 3 1
1 1
1 1
2 2
3 1

Sample Output 1

1/12

Explanation of Sample 1

Initially, the amount of each of the two types of balls are $(1,1)$. The probability of drawing a ball with color $1$ is $\frac{1}{2}$.
Before the second draw, the amounts of the two types of balls are $(2,1)$. The probability of drawing a ball with color $2$ is $\frac{1}{3}$.
Before the third draw, the amounts of the two types of balls are $(2,2)$. The probability of drawing a ball with color $1$ is $\frac{1}{2}$.
Therefore, the total probability for all three draws is $\frac{1}{12}$.

Sample Input 2

3 1 2
1 1 1
5 1

Sample Output 2

1/3

Problem translated to English by Alex.