Cô Mai là giáo viên chủ nhiệm, phụ trách tư vấn cho An về việc đăng ký lịch học cả năm. Trong chương trình học, có \(N\) môn được đánh số từ \(1\) đến \(N\). Mỗi môn có thể có một số môn tiên quyết: môn \(u\) là tiên quyết của môn \(v\) nghĩa là An phải hoàn thành môn \(u\) trước khi bắt đầu học môn \(v\).

Danh sách các tiên quyết có \(M\) ràng buộc, và đảm bảo không có vòng khép kín (không có chuỗi tiên quyết quay lại chính nó).

An muốn học đủ cả \(N\) môn. Hỏi có bao nhiêu thứ tự học (hoán vị của \(N\) môn) thỏa mãn tất cả ràng buộc tiên quyết? Hai thứ tự khác nhau nếu chuỗi môn học dọc đường khác nhau.

Vì số cách có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 20\), \(0 \le M \le N(N-1)/2\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả: môn \(u\) là tiên quyết của môn \(v\) (\(1 \le u, v \le N\), \(u \ne v\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số thứ tự học hợp lệ, modulo \(10^9 + 7\).

Ví dụ

Input:

4 3
1 2
1 3
2 4

Output:

2

Giải thích: Hai thứ tự hợp lệ là \(1 \to 2 \to 3 \to 4\) và \(1 \to 3 \to 2 \to 4\).

Ràng buộc

• \(1 \le N \le 20\)
• \(0 \le M \le N(N-1)/2\)
• Các tiên quyết đảm bảo không có vòng khép kín.
• Kết quả in theo modulo \(10^9 + 7\).