Đếm Đồ Thị

Cho một đồ thị vô hướng liên thông $G$ có $N$ đỉnh được đánh số từ $1$ đến $N$ và $M$ cạnh. Đồ thị có thể có khuyên (cạnh nối một đỉnh với chính nó) nhưng không có cạnh song song.

Định nghĩa hàm boolean $f_G(a,b)$ bằng true nếu tồn tại đường đi từ đỉnh $1$ đến đỉnh $a$ đi qua đúng $b$ cạnh (mỗi cạnh được tính mỗi lần đi qua), và false nếu không tồn tại.

Đếm số đồ thị vô hướng $G^{\prime }$ (có thể có khuyên, không có cạnh song song, trên $N$ đỉnh được đánh nhãn) thỏa mãn $f_{G^{\prime }}(a,b)=f_G(a,b)$ với mọi $a$ và $b$. Kết quả tính theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ — số lượng test case.

Mỗi test case bắt đầu bằng một dòng chứa hai số nguyên $N$ và $M$. Tiếp theo là $M$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x\le y\le N$) mô tả một cạnh trong $G$.

Các test case liên tiếp được phân cách bởi dòng trống.

Dữ liệu ra

Với mỗi test case, in ra một số nguyên duy nhất là số đồ thị $G^{\prime }$ thỏa mãn, modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le \frac{{10}^5}{4}$
• $2\le N\le {10}^2$
• $N-1\le M\le \frac{N^2+N}{2}$
• Tổng $N^2$ của tất cả các test case không vượt quá ${10}^5$

Ví dụ