Trong thành phố Freecontest có ~n~ ngôi nhà và ~m~ con đường một chiều, mỗi con đường đi từ một ngôi nhà ~a~ tới một ngôi nhà ~b~. Naul là một chàng trai đào hoa có ~n~ cô bạn gái, cô bạn gái thứ ~i~ ở ngôi nhà thứ ~i~. Mặc dù vậy, Naul chỉ thích hẹn hò với cô thứ ~1~ và cô thứ ~n~ nên Naul cần biết có bao nhiêu cách (bao nhiêu đường đi khác nhau) để đi từ nhà cô thứ nhất đến nhà cô thứ ~n~. Hãy trở thành người bạn tốt của Naul và giúp Naul tìm xem có bao nhiêu cách nhé!

Dữ liệu

• Dòng thứ nhất ghi hai số nguyên ~n, m~ ~(1 \le n \le 10^5,\ 1 \le m \le 2 \times 10^5)~ — lần lượt là số cô bạn gái và số lượng con đường một chiều.

• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le n)~ — con đường một chiều đi từ ngôi nhà ~a~ tới ngôi nhà ~b~. 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 cô gái ~i~ và ~j~ đều có thể đi đến nhà của nhau (đồ thị không có chu trình).

Kết quả

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

Ví dụ

Sample Input

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

Sample Output

3