Cho một biểu thức 2-CNF gồm \(N\) biến và \(M\) mệnh đề. Hãy đếm số phép gán giá trị true/false cho các biến thỏa mãn biểu thức.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(1 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i, b_i\) (\(-N \le a_i, b_i \le N\), \(a_i \neq 0\), \(b_i \neq 0\)).

Định dạng đầu ra

• In ra số phép gán thỏa mãn, kết quả có thể rất lớn nên in ra phần dư khi chia cho \(10^9 + 7\).

Ví dụ

Input:

2 2
1 2
-1 -2

Output:

2