Hành Trình Hamilton

Có $n$ thành phố và $m$ chuyến bay một chiều. Đếm số tuyến đường từ thành phố $1$ đến thành phố $n$ đi qua mỗi thành phố đúng một lần. In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$, mô tả chuyến bay từ $a$ đến $b$.

Dữ liệu ra

In một số nguyên duy nhất: số tuyến đường hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le 20$
• $1\le m\le n^2$
• $1\le a,b\le n$
• Có thể có nhiều chuyến bay trùng nhau giữa cùng một cặp thành phố. Mỗi chuyến bay là một lựa chọn riêng, nên hai tuyến đường đi qua cùng dãy thành phố nhưng dùng các chuyến bay khác nhau được tính là hai tuyến khác nhau. Dữ liệu cũng có thể chứa chuyến bay từ một thành phố đến chính nó.

Ví dụ