Hãy để tôi nói thẳng: mọi thứ đang không ổn chút nào. Những gì đáng lẽ phải là một buổi tối thư giãn cùng bạn bè đã trở nên tồi tệ: bạn bị tấn công bởi một kẻ quảng cáo nước hoa rẻ tiền, và cây xương rồng Argentina vô giá của bạn – thứ duy nhất bạn trân trọng – đã bị ném ra ngoài cửa sổ.

Ngay sau sự việc đó – hay nói đúng hơn là ngay khi có thể – bạn chạy xuống cầu thang để đánh giá thiệt hại. Và kìa, cây xương rồng vô giá của bạn vẫn còn sống! Dù có vài vết trầy xước, nhưng nó vẫn sống sót. Làm sao điều này có thể xảy ra? Phải chăng nó đã rơi vào thứ gì đó mềm mại? Tràn ngập niềm vui, bạn quyết định không tìm câu trả lời nữa. Tôi đã nói mọi thứ không ổn sao? Hãy quên điều đó đi, mọi thứ đều tuyệt vời – và đã đến lúc ăn mừng! Tất nhiên, trung tâm của buổi lễ kỷ niệm này sẽ là người bạn gai góc màu xanh của bạn.

Những ai chưa quen với thực vật học có thể cần một lời nhắc lại: xương rồng là một đồ thị liên thông, trong đó mỗi đỉnh nằm trên tối đa một chu trình. Để thêm phần không khí lễ hội, bạn quyết định tô màu mỗi đỉnh của cây xương rồng bằng một trong $k$ màu. Bạn muốn có nhiều sự tự do ở đây, nhưng bạn vẫn muốn tuân thủ quy tắc vàng của việc tô màu xương rồng: không hai đỉnh kề nhau nào được gán cùng một màu.

Một cách tô màu dường như là chưa đủ, vì vậy bạn quyết định rằng sau khi màu phai đi, bạn sẽ tô màu lại cây xương rồng hết lần này đến lần khác, mỗi lần sử dụng một cách tô màu khác nhau. Nhưng bạn sẽ có thể tiếp tục việc này trong bao lâu? Với mô tả về cây xương rồng của bạn và số $k$, hãy đếm số cách tô màu hợp lệ các đỉnh của cây xương rồng bằng $k$ màu. Vì kết quả có thể rất lớn, bạn chỉ cần tính phần dư của nó khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 50\,000$). Các mô tả của các bộ test sẽ theo sau.

Dòng đầu tiên của mỗi bộ test chứa ba số nguyên $n$, $m$ và $k$ ($1 \le n \le 300\,000$, $0 \le m \le 400\,000$, $2 \le k \le 10^9$) – số lượng đỉnh và cạnh của cây xương rồng, và số lượng màu.

$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i \neq v_i \le n$), tương ứng với các cạnh của cây xương rồng. Đảm bảo rằng đồ thị đã cho là một cây xương rồng và mỗi hai đỉnh được nối với nhau bởi tối đa một cạnh.

Tổng số đỉnh và cạnh trong tất cả các bộ test không vượt quá $3 \cdot 10^6$ và $4 \cdot 10^6$ tương ứng.

Dữ liệu ra

Với mỗi bộ test, hãy in ra một số nguyên duy nhất: số cách tô màu hợp lệ các đỉnh của cây xương rồng với $k$ màu, lấy phần dư modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

2
2 1 100
1 2
6 7 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4

Dữ liệu ra 1

9900
24