Một trò chơi có \(n\) màn chơi, được kết nối bởi \(m\) cổng dịch chuyển, và nhiệm vụ của bạn là đi từ màn \(1\) đến màn \(n\). Trò chơi đã được thiết kế sao không có chu trình có hướng trong đồ thị cơ bản. Bạn có thể hoàn thành trò chơi trong bao nhiêu cách?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng màn chơi và cổng dịch chuyển. Các màn chơi được đánh số \(1, 2, \ldots, n\).
• Sau này, có \(m\) dòng mô tả các cổng dịch chuyển. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một cổng dịch chuyển từ màn \(a\) đến màn \(b\).

Output

• In một số nguyên: số lượng cách bạn có thể hoàn thành trò chơi. Vì kết quả có thể lớn, hãy in nó chia lấy dư cho \(10^9 + 7\).

Constraints

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

Example

Sample input

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

Sample output

3