Các Tuyến Đường Trong Game

Có $n$ màn chơi và $m$ cổng dịch chuyển một chiều tạo thành đồ thị phi chu trình (DAG). Đếm số đường đi từ màn $1$ đến màn $n$, lấy 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$, $b$ — cổng dịch chuyển từ $a$ đến $b$.

Dữ liệu ra

In số đường đi từ màn $1$ đến màn $n$ modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$

Ví dụ