Cây khung XOR

Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh có trọng số. Mỗi cạnh nối hai đỉnh khác nhau, và không có hai cạnh nào cùng nối một cặp đỉnh.

Cấu trúc của đồ thị được đảm bảo có tính chất đặc biệt sau:

• Mỗi đỉnh thuộc nhiều nhất một chu trình đơn (chu trình đơn là một đường đi khép kín xuất phát và kết thúc tại cùng một đỉnh, đi qua các đỉnh khác không quá một lần).
• Đồ thị có nhiều nhất $42$ chu trình đơn như vậy.

Bạn cần chọn ra một tập cạnh sao cho tất cả các đỉnh vẫn liên thông (tức là một cây khung của đồ thị). "Chi phí" của một tập cạnh được định nghĩa là XOR của trọng số các cạnh trong tập:

$$\text{Cost}=W_{i_1}\oplus W_{i_2}\oplus \dots \oplus W_{i_k}$$

Hãy tìm:

1. Giá trị chi phí nhỏ nhất có thể.
2. Số cách chọn tập cạnh đạt được chi phí nhỏ nhất đó, lấy dư cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ — số đỉnh và số cạnh.
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $U$, $V$, $W$ mô tả một cạnh nối đỉnh $U$ với đỉnh $V$ có trọng số $W$.

Dữ liệu ra

In ra hai số nguyên trên một dòng: chi phí nhỏ nhất và số cách chọn (mod ${10}^9+7$).

Ràng buộc

• $1\le N\le 100000$
• $1\le M\le 100041$
• $1\le U\ne V\le N$
• $1\le W\le 100000$
• Đồ thị liên thông.
• Mỗi đỉnh nằm trong nhiều nhất một chu trình đơn, và tổng số chu trình đơn không vượt quá $42$.

Ví dụ