Những Tuyến Đường Qua Cổng Dịch Chuyển · canuc80k3211

Một trò chơi có $n$ cửa ải, được đánh số từ $1$ đến $n$ , cùng $m$ cổng dịch chuyển một chiều. Mỗi cổng cho phép đi từ một cửa ải $a$ đến một cửa ải $b$ .

Hệ thống được thiết kế sao cho không có chu trình có hướng: sau khi đi qua ít nhất một cổng, người chơi không thể quay lại cửa ải đã từng đứng trước đó.

Người chơi bắt đầu ở cửa ải $1$ và hoàn thành trò chơi khi tới cửa ải $n$ . Một cách hoàn thành là một dãy các cổng được sử dụng liên tiếp, đúng theo chiều của từng cổng. Hai cách được xem là khác nhau nếu tại một bước nào đó chúng sử dụng hai cổng khác nhau. Vì vậy, nếu input chứa nhiều cổng cùng nối từ $a$ đến $b$ , mỗi cổng vẫn là một lựa chọn riêng.

Hãy đếm số cách hoàn thành trò chơi. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia cho $1000000007$ .

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ , mô tả một cổng dịch chuyển một chiều từ $a$ đến $b$ .

Output

In một số nguyên: số cách đi từ cửa ải $1$ đến cửa ải $n$ , lấy modulo $1000000007$ .

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq m \leq 2 \cdot 1 0^{5}$ .
$1 \leq a, b \leq n$ .
Đồ thị tạo bởi các cổng dịch chuyển không chứa chu trình có hướng.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 10$ và $m \leq 30$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Ba cách là $1 \to 2 \to 5, 1 \to 2 \to 4 \to 5$ và $1 \to 3 \to 4 \to 5$ .

Test 2

Input

Output

Giải thích: Từ cửa ải $1$ chỉ có thể đi tới $2$ rồi $3$ ; không có cổng nào đưa người chơi từ phần này tới cửa ải $6$ , nên không có cách hoàn thành.

Ý tưởng: Đặt ways[v] là số cách đi từ cửa ải 1 tới cửa ải v, lấy modulo 1 000 000 007. Khởi tạo ways[1] = 1; các giá trị khác bằng 0.
Ý tưởng: Ta xử lý các cửa ải theo thứ tự topo bằng thuật toán Kahn. Khi lấy một cửa ải u ra khỏi hàng đợi, mọi cổng đi vào u đã được xét. Với mỗi cổng u → v, mọi cách tới u có thể nối thêm cổng này để tạo một cách tới v, nên cập nhật
Ý tưởng:

text ways[v] = (ways[v] + ways[u]) mod 1 000 000 007. - Ý tưởng: Nếu có nhiều cổng cùng nối u tới v, vòng lặp xử lý từng cổng một, đúng với việc mỗi cổng là một lựa chọn riêng. - Tính đúng đắn: Bổ đề 1. Khi đỉnh u được lấy ra theo thứ tự topo, ways[u] bằng số cách đi từ 1 tới u. - Tính đúng đắn: Chứng minh. Mọi cách không rỗng tới u có đúng một cổng cuối cùng x → u. Do x đứng trước u trong thứ tự topo, số cách tới x đã đúng và đã được cộng vào ways[u]. Các nhóm được phân biệt bởi cổng cuối cùng, nên phép cộng không bỏ sót và không đếm trùng. Riêng tại đỉnh 1, giá trị khởi tạo 1 biểu diễn trạng thái bắt đầu. ∎ - Tính đúng đắn: Bổ đề 2. Mỗi lần xử lý cổng u → v, thuật toán cộng chính xác số cách có cổng cuối cùng là cổng đó. - Tính đúng đắn: Chứng minh. Ghép cổng u → v vào từng cách tới u tạo ra đúng ways[u] cách tới v, và mọi cách sử dụng cổng này được tạo như vậy. ∎ - Tính đúng đắn: Định lý. Thuật toán in đúng số cách hoàn thành trò chơi modulo 1 000 000 007. - Tính đúng đắn: Chứng minh. Theo Bổ đề 1, sau khi xử lý topo, ways[n] là số cách từ 1 tới n. Mọi phép cộng đều được lấy modulo, nên giá trị in ra đúng theo yêu cầu. ∎ - Độ phức tạp: Mỗi cửa ải và mỗi cổng được xử lý hằng số lần. Thời gian là O(n + m), bộ nhớ là O(n + m).