Đất nước XYZ có n thành phố, được đánh số từ 1 đến n và có m con đường một chiều nối giữa hai thành phố. Yêu cầu: Đếm số cách đi từ thành phố 1 đến thành phố thứ n.

Dữ liệu

• Dòng thứ nhất ghi hai số nguyên n, m (1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 2 × 10^5 ) − lần lượt là số thành phố và số lượng con đường một chiều.

• m dòng tiếp theo, dòng thứ i gồm hai số nguyên u và v (1 ≤ u, v ≤ n) − con đường nối thành phố u tới thành phố v;

Dữ liệu luôn đảm bảo không tồn tại cặp chỉ số (i, j) nào mà cả hai thành phố i và j đều có thể đi đến được với nhau.

Kết quả:

In ra số cách để đi từ thành phố 1 đến thành phố thứ n. Kết quả lấy dư theo module 10^9 + 7

Sample Input

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

Sample Output

3