Có một đồ thị vô hướng với ~n~ đỉnh và ~m~ cạnh, mỗi đỉnh được đánh số từ ~1~ đến ~n~. Bạn cần giải ~q~ truy vấn, truy vấn thứ ~i~ bạn được cho một số ~k_i~ tức trong truy vấn đó bạn chỉ có ~k_i~ loại màu.

Yêu cầu: Với mỗi truy vấn tô màu mỗi đỉnh của đồ thị trên sao cho hai đỉnh có cạnh nối không cùng màu. Tính số cách tô màu hợp lệ, chia lấy dư cho ~10^9+7~

Input

• Dòng đầu tiên gồm ba số nguyên ~n, m, q(1 \le n \le 10^5, 0 \le m \le min(10^5,n*(n-1)/2),1 \le q \le 1000)~ ~-~ lần lượt là thị số lượng đỉnh, số lượng cạnh và số lượng truy vấn.
• ~m~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~u_i, v_i~ - có một cạnh nối giữa chúng. Đảm bảo không có cạnh trùng lặp.
• ~q~ dòng tiếp theo mỗi dòng gồm một số nguyên ~k_i(1 \le k_i \le 10^9)~ ~-~ trong truy vấn đó có ~k_i~ loại màu.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~ chia lấy dư cho ~10^9+7~.

Sample Input

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

Sample Output

2
48
324
1280

Subtask

• Có ~18\%~ số test thỏa mãn: ~1 \le n,k \le 8, 1 \le q \le 50~.
• Có ~26\%~ số test thỏa mãn: ~1 \le n \le 15~.
• Có ~20\%~ số test thỏa mãn: ~1 \le m \le 24~.
• Có ~36\%~ số test thỏa mãn: Mỗi đỉnh có đúng hai cạnh nối với nó.

Hint

• Brute đi nào