Cây khung xor

Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh. Cạnh thứ $i$ nối hai đỉnh $U_i\ne V_i$ và có trọng số $W_i$. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.

Đồ thị có thêm một tính chất đặc biệt: mỗi đỉnh nằm trên nhiều nhất một chu trình đơn, và toàn bộ đồ thị có nhiều nhất $42$ chu trình đơn.

Bạn cần giữ lại một số cạnh sao cho đồ thị vẫn liên thông, đồng thời số cạnh giữ lại là ít nhất có thể (nói cách khác, tập cạnh giữ lại tạo thành một cây khung). Chi phí của một cách giữ lại không phải là tổng trọng số, mà là xor của trọng số các cạnh được giữ: nếu các cạnh giữ lại có trọng số $A_1,A_2,\dots ,A_k$ thì chi phí bằng $A_1\oplus A_2\oplus \dots \oplus A_k$.

Hãy tìm chi phí nhỏ nhất có thể, và đếm số cây khung đạt được chi phí nhỏ nhất đó. Hai cây khung được coi là khác nhau nếu tập cạnh của chúng khác nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $U_i$, $V_i$, $W_i$ mô tả cạnh thứ $i$.

Dữ liệu ra

Một dòng chứa hai số nguyên: chi phí nhỏ nhất, và số cây khung đạt chi phí đó lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le N\le 100000$
• $1\le M\le 100041$
• $1\le U_i,V_i\le N$, $U_i\ne V_i$
• $1\le W_i\le 100000$
• Đồ thị liên thông, không có hai cạnh nối cùng một cặp đỉnh
• Mỗi đỉnh thuộc nhiều nhất một chu trình đơn, và có nhiều nhất $42$ chu trình đơn

Ví dụ