题目描述
Problem Background
In the morning at a kindergarten, teachers need to distribute toys to the children.
Problem Description
Some children play with toys alone, while others play in pairs.
There are $n$ children, and these $n$ children can be divided into $m$ pairs.
There are $k$ types of toys to be distributed to these children, and it must be ensured that the toys given to children within the same pair are different.
Determine the total number of distribution schemes.
Since there are many days for distribution, there are $z$ sets of queries. In these $z$ sets of queries, $n$, $m$, and the corresponding pairs remain unchanged, but $k$ varies.
Input Format
The first line contains three integers $n$, $m$, and $z$, representing the number of children, the number of pairs, and the number of queries, respectively.
The $n$ 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 a query.
Output Format
$z$ lines, each containing one integer representing the number of distribution schemes.
The answer should be modulo $10^9+7$.
Sample Input and Output
Input Sample #1
4 4 1
1 2
2 3
1 3
3 4
3
Output Sample #1
12
Input Sample #2
5 10 2
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
5
6
Output Sample #2
120
720
Input Sample #3
11 40 1
8 1
4 1
3 8
2 6
9 8
11 5
2 5
2 1
11 4
10 6
11 10
9 7
10 4
6 9
9 10
2 11
6 7
8 2
10 8
3 6
11 9
1 10
4 3
6 11
3 11
4 5
8 7
10 3
11 7
9 2
8 6
2 3
3 7
8 4
9 5
4 9
7 2
5 10
10 2
6 4
15
Output Sample #3
142679253
Notes
Sample Explanation
Additional sample explanations can be found in the attached files sample 1/2.in and sample 1/2.out.
Data Size and Constraints
This problem uses subtask testing.
- 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): A child is exactly in two pairs.
For $100\%$ of the data, $1 \le n \le 10^5$, $0 \le m \le \min(10^5, \frac{n^2-n}{2})$, $1 \le z \le 1000$, $1 \le k \le 10^9$.
For $50\%$ of the data, $z = 1$.
Notes
Translated from POI 2019 D Przedszkole.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分