Huy là một học sinh có nhiều hứng thú về đồ thị. Trong quá trình nghiên cứu về chủ đề này, Huy đã nghĩ ra một dạng đồ thị dựa trên tên anh ấy, gọi là đồ thị H. Một đồ thị H là một đồ thị vô hướng gồm \(6\) đỉnh phân biệt được kí hiệu lần lượt là \(A, B, C, D, E, F\) và \(5\) cạnh:

• \(C\) có cạnh nối với \(A, B\);
• \(D\) có cạnh nối với \(E, F\);
• \(C\) và \(D\) có cạnh nối với nhau.

Là một người cùng nghiên cứu đồ thị với Huy, bạn được Huy cho một đồ thị \(G\) vô hướng gồm \(n\) đỉnh và \(m\) cạnh sao cho mỗi cạnh nối hai đỉnh khác nhau và giữa hai đỉnh bất kỳ có tối đa một cạnh nối giữa chúng. Nhiệm vụ của bạn là giúp Huy đếm xem có bao nhiêu đồ thị con khác nhau của \(G\) thỏa mãn điều kiện của một đồ thị H.

Biết rằng:

• Đồ thị con của đồ thị \(G=(V,E)\) là đồ thị \(H=(W,F)\), sao cho \(W \subseteq V\) và \(F\subseteq E\).
• Hai đồ thị con được gọi là khác nhau khi tồn tại cạnh xuất hiện trong đồ thị này nhưng không xuất hiện trong đồ thị còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \(\left(1 \leq n \le 10^5, 0 \leq m \le \min\left(\frac{n \times (n-1)}{2}, 4 \times 10^5\right)\right)\) lần lượt là số đỉnh và số cạnh của đồ thị.
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u \neq v \le n)\) cho biết có một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

• Một số nguyên duy nhất là số lượng đồ thị con của \(G\) là đồ thị H sau khi chia lấy dư cho \(10^9+7\).

Example

6 7
1 2
2 3
3 4
4 5
5 6
6 1
6 3

1

6 9
1 2
2 3
3 4
4 5
5 6
6 1
6 3
3 5
2 4

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(m = n - 1\) và giữa hai đỉnh bất kỳ đều tồn tại đường đi giữa chúng.
• Subtask \(3\) (\(20\%\) số điểm): \(n, m \leq 5000\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^{4}\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.