Description

Source Problem: POI XXVII - I etap 「Przedszkole」

Each morning the kindergarten teacher hands out toys to the children. To keep everything in order, each of the $n$ children receives exactly one toy. Each child may either play on their own or in pair together with another child, but only if the two like each other.

The teacher has $k$ kinds of toys. She is wondering how many different ways there are to distribute the toys among the children in such a way that every two children who like each other receive different kinds (so that they have two kinds to play with should they form a pair).

Input Format

In the first input line, there is a triplet of integers $n$, $m$, $z$, separated by single spaces, which respectively specify: the number of children in the kindergarten, the number of pairs of children who like each other, and the number of queries.

The $m$ lines that follow specify the pairs of children who like each other: each such line contains two positive integers ai and bi which are the numbers of the two children who like each other. For simplicity, we number children from $1$ to $n$. No pair appears more than once on input.

Finally, the last $z$ lines contain the queries: the $i$-th of these contains an integer $k_i$.

Output Format

Exactly $z$ lines should be printed to output: the $i$-th of these should contain the number of ways the toys can be distributed among the children if there are $k_i$ kinds. The numbers should be reported modulo $10^9 + 7$ (i.e., the remainder of division of the actual number by $10^9 + 7$ should be printed).

4 4 1
1 2
2 3
1 3
3 4
3

12

Additional Samples

See prz/prz*.in and prz/prz*.out for additional samples.

• Additional Sample 1: $n = 5, m = 10$ (all children like each other), two queries for $k \in \{5, 6\}$;
• Additional Sample 2: $n = 11, m = 40$, query for $k = 15$;
• Additional Sample 3: $n = 100, m = 15$, five queries for random $k \in [10, 100]$;
• Additional Sample 4: $n = 100, m = 100$, the pairs of children who like each other are No. $i$ and No. $i + 1$ for $1 \leq i < 100$ as well as No. $100$ and No. $1$; three queries for $k \in \{5, 10, 15\}$.

Constraints

The set of tests consists of the following subsets. Within each subset, there may be several tests. Within each subset, at least $50\%$ of the score is awarded for tests in which $z = 1$.

For all data, it is guaranteed that $1 \le n \le 10^5, 0 \le m \le \min(10^5, n(n-1)/2), 1 \le z \le 1000, 1 \le a_i, b_i \le n, 1 \le k_i \le 10^9$.