Tý đang nghiên cứu luồng thông tin điều hành trong tập đoàn. Mạng lưới gồm \(N\) phòng ban (đánh số từ \(1\) đến \(N\)) và \(M\) kênh truyền tin một chiều.

Một lộ trình thông tin từ phòng \(1\) đến phòng \(N\) là một dãy các phòng ban \(p_1 = 1, p_2, \dots, p_k = N\) sao cho có kênh truyền tin một chiều từ \(p_i\) đến \(p_{i+1}\) với mọi \(i\).

Tý muốn đếm số lượng lộ trình thông tin khác nhau từ phòng \(1\) đến phòng \(N\) trên mô hình tinh gọn (đồ thị thu nhỏ). Trong mô hình này, mỗi cụm liên lạc độc lập được coi là một siêu đỉnh, và các lộ trình được xét trên đồ thị thu nhỏ.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) mô tả kênh truyền tin một chiều từ \(u\) đến \(v\).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượng lộ trình khác nhau trên đồ thị thu nhỏ từ siêu đỉnh chứa phòng \(1\) đến siêu đỉnh chứa phòng \(N\). Kết quả lấy modulo \(10^9 + 7\).

Ví dụ

Input:

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

Output:

1