Cơn Ác Mộng Euclid

Cho một tập $S$ gồm $n$ vectơ trên trường ${\mathbb{Z}}_2$ với $m$ chiều. Mỗi vectơ có $m$ tọa độ, mỗi tọa độ bằng $0$ hoặc $1$. Phép cộng hai vectơ $u+v=w$ được định nghĩa $w_i=(u_i+v_i)mod2$.

Bạn được cộng tùy ý một tập con của $S$ (kể cả tập rỗng — kết quả là vectơ $0$). Gọi $T$ là tập tất cả các vectơ có thể tạo được bằng cách cộng một tập con nào đó của $S$.

Mỗi vectơ trong $S$ có không quá 2 tọa độ bằng 1.

Hãy tính:

1. $|T|$ theo modulo ${10}^9+7$.
2. Một tập con $S^{\prime }\subseteq S$ có kích thước nhỏ nhất sao cho mọi vectơ trong $T$ vẫn có thể tạo được bằng cách cộng các vectơ trong $S^{\prime }$.

Nếu có nhiều tập $S^{\prime }$ kích thước nhỏ nhất, hãy chọn tập có dãy chỉ số nhỏ nhất theo thứ tự từ điển. So sánh hai tập có cùng kích thước: viết các chỉ số phần tử theo thứ tự tăng dần thành dãy $a_1<a_2<\dots$ và $b_1<b_2<\dots$; $A$ nhỏ hơn $B$ về thứ tự từ điển nếu tồn tại $i$ sao cho $a_j=b_j$ với mọi $j<i$ và $a_i<b_i$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• $n$ dòng tiếp theo mô tả các vectơ. Mỗi dòng bắt đầu bằng số nguyên $k$ ($1\le k\le 2$), tiếp theo là $k$ số nguyên phân biệt $x_1,\dots ,x_k$ ($1\le x_i\le m$), biểu diễn vectơ có giá trị $1$ tại các tọa độ $x_1,\dots ,x_k$ và $0$ ở các vị trí còn lại.

Không có hai vectơ nào trong $S$ trùng nhau.

Dữ liệu ra

• Dòng đầu tiên in hai số: $|T|mod({10}^9+7)$ và $|S^{\prime }|$.
• Dòng thứ hai in $|S^{\prime }|$ chỉ số của các phần tử trong $S^{\prime }$ theo thứ tự tăng dần (đánh số từ $1$ theo thứ tự đầu vào).

Ràng buộc

• $1\le n,m\le 5·{10}^5$.
• $1\le k\le 2$.
• $1\le x_i\le m$.

Ví dụ