Đếm số đường đi ngắn nhất

Thành phố Huế có ~N~ quán ăn được đánh số từ ~1~ đến ~N~ và ~M~ con đường nối giữa chúng đánh số từ ~1~ đến ~M~. Sử dụng con đường thứ ~i~ bạn có thể đi từ quán ăn ~a_i~ đến quán ăn ~b_i~ hoặc ngược lại trong ~1~ giờ.

Hỏi có bao nhiêu con đường mà bạn có thể đi từ quán ăn số ~1~ đến quán ăn số ~N~ càng sớm càng tốt.

Input

Dòng đầu tiên chứa hai số nguyên dương ~N, M~ thỏa ~2 \le N \le 10^5, 0 \le M \le 2.10^5~.

~M~ dòng tiếp theo chứa ~2~ số nguyên ~a_i, b_i~ thỏa ~1 \le a_i < b_i \le N~ là đường đi thứ ~i~ nối giữa hai quán ăn ~a_i~ và ~b_i~.

Output

In ra kết quả cần tìm, do số lớn nên cần modulo cho ~10^9+7~. Nếu không có kết quả in ~0~.

Samples

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

2

Note

Có ~2~ đường đi ngắn nhất với thời gian ~2~ giờ là: 1->2->4 và 1->3->4.