Cơ quan Hàng không Vũ trụ đang xây dựng một mạng lưới liên kết lượng tử gồm \(N\) trạm không gian.
Mạng lưới này liên tục biến động qua \(Q\) sự kiện. Tại mỗi sự kiện, một trong hai tình huống sẽ xảy ra:

• + u v: Khởi tạo một liên kết phản vật chất giữa trạm \(u\) và trạm \(v\).
• - u v: Ngắt bỏ liên kết phản vật chất giữa trạm \(u\) và trạm \(v\) (đảm bảo liên kết này đang tồn tại).

Một hệ thống được gọi là "Cân bằng" nếu toàn bộ đồ thị mạng lưới tại thời điểm đó là một Đồ thị hai phía (Bipartite Graph) (không tồn tại bất kỳ chu trình lẻ nào). Nếu hệ thống mất cân bằng, nó sẽ sụp đổ.

Nếu hệ thống đang cân bằng, các kỹ sư cần sơn \(N\) trạm bằng 2 màu (Xanh và Đỏ) sao cho không có 2 trạm nào cùng màu được nối với nhau.

Yêu cầu: Sau mỗi sự kiện, hãy xác định số cách sơn màu thỏa mãn điều kiện. Nếu hệ thống mất cân bằng, số cách sơn màu bằng \(0\). Vì kết quả có thể rất lớn, hãy in ra phần dư của số cách sơn màu khi chia cho \(10^9 + 7\).

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một ký tự + hoặc - và hai số nguyên \(u, v\) mô tả một sự kiện.
• \(1 \le N, Q \le 10^5\).
• \(1 \le u, v \le N, u \neq v\)

Output

• In ra \(Q\) dòng, mỗi dòng là số lượng cách sơn màu hợp lệ cho mạng lưới ngay sau sự kiện tương ứng (modulo \(10^9+7\)).

Example

4 8

+ 1 2
+ 2 3
+ 3 4
+ 4 1
+ 1 3
- 1 2
- 4 1
- 1 3

8
4
2
2
0
0
2
4