CSES - Hamiltonian Flights | Chuyến bay Hamilton

Xem PDF

Điểm: 1800 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(n\) thành phố và \(m\) chuyến bay kết nối giữa chúng. Bạn muốn đi từ Syrjälä đến Lehmälä để bạn đến thăm mỗi thành phố đúng một lần. Có bao nhiêu tuyến đường khả thi?

Input

  • Dòng đầu tiên là hai số nguyên \(n\)\(m\): số thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
  • Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng gồm hai số nguyên \(a\)\(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay đều là chuyến bay một chiều.

Output

  • In ra một số nguyên: số tuyến đường theo modulo \(10^9 + 7\).

Constraints

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

Example

Test 1

Input
4 6
1 2
1 3
2 3
3 2
2 4
3 4
Output
2

Bình luận

Không có bình luận nào.