Tam giác tình yêu

Có $n$ nhân vật được đánh số từ $1$ đến $n$. Mỗi cặp nhân vật khác nhau hoặc yêu nhau, hoặc ghét nhau (không có trạng thái trung lập), và quan hệ này luôn đối xứng.

Một bộ ba nhân vật phân biệt $\{A,B,C\}$ được gọi là hợp lệ nếu trong ba cặp $(A,B),(B,C),(C,A)$ có đúng một cặp yêu nhau hoặc cả ba cặp đều yêu nhau. Cấu hình quan hệ trên cả $n$ nhân vật được gọi là hợp lệ nếu mọi bộ ba nhân vật phân biệt đều hợp lệ.

Bạn được cho biết trước $m$ quan hệ giữa một số cặp nhân vật. Hỏi có bao nhiêu cách điền tất cả các quan hệ còn lại để cấu hình thu được hợp lệ. Hai cách điền là khác nhau nếu tồn tại một cặp có quan hệ khác nhau ở hai cách. In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i,b_i,c_i$ mô tả một quan hệ đã biết: nếu $c_i=1$ thì $a_i$ và $b_i$ yêu nhau, ngược lại ($c_i=0$) thì họ ghét nhau. Mỗi cặp nhân vật được mô tả không quá một lần và $a_i\ne b_i$.

Dữ liệu ra

• In ra số cách điền hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $3\le n\le {10}^5$
• $0\le m\le {10}^5$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• $c_i\in \{0,1\}$

Ví dụ