Background

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

Problem Description

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.

Input Format

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 Format

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

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

12

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

120
720

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

142679253

Hint

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 D Przedszkole.

Translated by ChatGPT 5