P6662 [POI 2019/2020 R1] Przedszkole / Kindergarten.

In the morning at the kindergarten, teachers need to hand out toys to children.

Some children play with toys alone, and some children play in pairs. Now there are $n$ children, and these $n$ children can be grouped into $m$ pairs. There are $k$ types of toys to be handed out to these children. It must be guaranteed that, within each pair, the two children receive different toys. Find the total number of possible distribution plans. Because toys need to be handed out on many days, there are $z$ queries. In these $z$ queries, $n$, $m$, and the given pairs stay the same, while $k$ changes.

The first line contains three integers $n,m,z$, representing the number of children, the number of pairs, and the number of queries. The children are numbered from $1$ to $n$. The next $m$ lines each contain two integers, representing a pair of children. The next $z$ lines each contain one integer $k$, representing one query.

Output $z$ lines, each containing one integer, representing the number of distribution plans. The answer should be taken modulo $10^9+7$.

#### Sample Explanation Two additional samples can be found in the attached files sample 1/2.in and sample 1/2.out. #### Constraints **This problem uses bundled tests.** - Subtask 1 (8 pts): $n,k \le 8$, $z \le 50$. - Subtask 2 (26 pts): $n \le 15$. - Subtask 3 (33 pts): $m \le 24$. - Subtask 4 (33 pts): each child appears in exactly two pairs. For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le m \le \min(10^5,\dfrac{n^2-n}{2})$, $1 \le z \le 1000$, $1 \le k \le 10^9$. For $50\%$ of the testdata, $z=1$. #### Note Translated from [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) D [Przedszkole](https://sio2.mimuw.edu.pl/c/oi27-1/p/prz/). Translated by ChatGPT 5