Description

Pòlya obtained a marvelous pocket inscribed with symbols beyond human understanding. Fascinated, he pondered and discovered a magical model (later called the "Pòlya model"). To vividly teach this model, he had his students play a virtual game: at the beginning, put $a_1$ balls of color $1$, $a_2$ balls of color $2$, …, and $a_t$ balls of color $t$ into the bag, where $a_i \in \mathbb Z^+$ ($1 \le i \le t$).

After the game starts, repeat the following operation strictly each time:

Randomly draw one ball from the bag (all balls in the bag are equally likely to be drawn), Pòlya observes the color of this ball and puts it back, then adds $d$ more balls of the same color into the pocket.

Let $c_i$ be the color of the ball drawn on the $i$-th draw ($1 \le c_i \le t$). A single game run produces a color sequence $(c_1, c_2, \ldots, c_n, \ldots)$. Pòlya tells all students the initial counts of balls of the $t$ colors, namely $a_1, a_2, \ldots, a_t$. Then he asks the students: what is the probability that a single run produces a color sequence satisfying

$$c_{x_1}=y_1, c_{x_2}=y_2, \ldots, c_{x_n}=y_n \, ?$$

Here $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, \ldots, a_t, x_1, y_1, x_2, y_2, \ldots, x_n, y_n)$, you need to answer the probability of the following event: “for all $k$ ($1 \le k \le n$), the color of the $x_k$-th draw is $y_k$.”

Input Format

• The first line contains three positive integers $t, n, d$.
• The second line contains $t$ positive integers $a_1, a_2, \ldots, a_t$, representing the number of balls of each of the $t$ colors at the beginning of the game.
• Each of the next $n$ lines contains two positive integers $x_i, y_i$, indicating that on the $x_i$-th draw the color is $y_i$.

Output Format

Output the probability as a fraction (this probability is clearly rational). The output contains one line in the format: numerator/denominator. It must be in lowest terms (the numerator and denominator are coprime). In particular, if the probability is $0$, output 0/1; if the probability is $1$, output 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

Hint

[Sample Explanation #1]

Initially, the counts of the two colors are $(1, 1)$, so the probability of drawing a ball of color $1$ is $1/2$. Before the second draw, the counts become $(2, 1)$, so the probability of drawing a ball of color $2$ is $1/3$. Before the third draw, the counts become $(2, 2)$, so the probability of drawing a ball of color $1$ is $1/2$. Therefore, the total probability of the three draws is $1/12$.

Constraints

For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5