Trong một vương quốc, các thành phố được kết nối với nhau bằng những con đường đơn giản. Để quản lý giao thông tốt hơn và xác định số tuyến đường có thể đi giữa các thành phố, nhà quản lý đã nhờ bạn hỗ trợ thực hiện một số phép tính.

Cụ thể, vương quốc có ~N~ thành phố và ~M~ con đường. Mỗi con đường nối trực tiếp hai thành phố và có trọng số là ~1~. Nhà quản lý đã chuẩn bị một tập truy vấn để tính toán các tuyến đường cụ thể.

Với mỗi truy vấn, bạn được cho ba số nguyên ~u~, ~v~, và ~K~, và bạn phải tính số đường đi từ thành phố ~u~ đến thành phố ~v~ với tổng trọng số chính xác bằng ~K~. Bạn có thể đi qua lại cùng một thành phố nhiều lần nếu cần để đạt được tổng trọng số yêu cầu.

Nhiệm vụ của bạn là giúp nhà quản lý trả lời các truy vấn này. Với mỗi truy vấn, hãy tính số đường đi từ thành phố ~u~ đến thành phố ~v~ có trọng số bằng ~K~, và trả về kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào:

1. Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(M \leq \frac{N(N-1)}{2})~.
2. ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~, biểu thị một con đường trực tiếp giữa thành phố ~u~ và thành phố ~v~ ~(1 \leq u \leq v \leq N)~.
3. Dòng tiếp theo chứa một số nguyên ~Q~, là số lượng truy vấn.
4. ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, và ~K~, biểu thị một truy vấn.

Dữ liệu ra:

• ~Q~ dòng, mỗi dòng chứa một số nguyên: số đường đi từ thành phố ~u~ đến thành phố ~v~ có tổng trọng số bằng ~K~, theo modulo ~10^9 + 7~.

Ví dụ nhập

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

Ví dụ xuất

3
1

Ghi chú

Với truy vấn ~1~, các đường đi là:

• ~1 \to 3 \to 1 \to 3~
• ~1 \to 3 \to 2 \to 3~
• ~1 \to 3 \to 4 \to 3~

Với truy vấn ~2~, đường đi là:

• ~2 \to 3 \to 1~

Giới hạn:

• Subtask ~1~ (~40%~ số điểm): ~N, Q, K \leq 10~.
• Subtask ~3~ (~15%~ số điểm): ~N \leq 10, K \leq 20,~ và ~Q \leq 10^5~.
• Subtask ~4~ (~15%~ số điểm): ~N \leq 100, K \leq 10,~ và ~Q \leq 20~.
• Subtask ~5~ (~15%~ số điểm): ~N \leq 100, K \leq 50,~ và ~Q \leq 10^5~.
• Subtask ~6~ (~15%~ số điểm): ~N \leq 100, K \leq 10^5,~ và ~Q \leq 10~.