Bạn được cho một đồ thị vô hướng có \(n\) nút và \(m\) cạnh.

Chúng tôi xem xét các đồ thị con có tất cả các nút của đồ thị gốc và một số cạnh của nó. Một đồ thị con được gọi là Euler nếu mỗi nút có bậc chẵn.

Nhiệm vụ của bạn là đếm số lượng đồ thị con Euler chia lấy dư cho \(10 ^ 9 + 7\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng nút và cạnh. Các nút được đánh số \(1, 2 \ldots, n\).
• Sau này, có \(m\) dòng mô tả các cạnh. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một cạnh giữa các nút \(a\) và \(b\). Có nhiều nhất một cạnh giữa hai nút và mỗi cạnh nối hai nút phân biệt.

Output

• In số lượng đồ thị con Euler chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq n \leq 10 ^ 5\)
• \(0 \leq m \leq 2 \cdot 10 ^ 5\)
• \(1 \leq a, b \leq n\)

Example

Sample input

4 3
1 2
1 3
2 3

Sample output

2

Note

Bạn có thể giữ hoặc loại bỏ tất cả các cạnh, vì vậy có thể có hai đồ thị con Euler.