Có \(n\) điểm tham quan và \(m\) đường đi giữa các điểm tham quan. Hỏi có bao nhiêu cách đi tham quan từ điểm số \(1\) đến điểm \(n\) sao cho đi qua tất cả các điểm, mỗi điểm đúng \(1\) lần.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(m\).
• \(m\) dòng tiếp theo, mỗi dòng có \(2\) số \(a\) và \(b\). Tức là có đường đi từ điểm \(a\) đến điểm \(b\).

Output

• Số lượng đường đi modulo cho \(10^9+7\)

Ràng buộc

• \(2 \le n \le 20\)
• \(1 \le m \le n^2\)
• \(1 \le a,b \le n\)

Input 1

4 6
1 2
1 3
2 3
3 2
2 4
3 4

Output 1

2