Đường đi trong trò chơi

Trong một buổi giải trí cuối tuần, FullHouse Dev đã tìm thấy một trò chơi thú vị. Trò chơi có nhiều màn chơi được kết nối với nhau bởi các cổng dịch chuyển một chiều. Nhiệm vụ của họ là tìm ra có bao nhiêu cách để di chuyển từ màn 1 đến màn cuối cùng.

Bài toán

Trò chơi có \(n\) màn chơi được kết nối bởi \(m\) cổng dịch chuyển một chiều. Các cổng được thiết kế sao cho không tạo thành chu trình có hướng trong đồ thị. Nhiệm vụ là tìm số cách có thể để hoàn thành trò chơi (di chuyển từ màn 1 đến màn \(n\)).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng màn chơi và số lượng cổng dịch chuyển. Các màn chơi được đánh số từ 1 đến \(n\).
• \(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 từ màn \(a\) đến màn \(b\).

OUTPUT FORMAT:

• In ra một số nguyên: số cách có thể để hoàn thành trò chơi. Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9+7\).

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

4 5
1 2
2 4
1 3
3 4
1 4

OUTPUT

3

Giải thích

Có 3 cách để di chuyển từ màn 1 đến màn 4:

• Cách 1: 1 → 2 → 4
• Cách 2: 1 → 3 → 4
• Cách 3: 1 → 4 (trực tiếp)