Một con chuột ở đỉnh \(1\) của đồ thị có hướng gồm \(N\) đỉnh và \(M\) cạnh. Mỗi bước, chuột di chuyển ngẫu nhiên đều đến một đỉnh kề (nếu có nhiều cạnh đi, chọn ngẫu nhiên một cạnh). Nếu đến đỉnh \(N\), chuột dừng lại. Tính xác suất chuột đến được \(N\). Kết quả modulo \(10^9+7\).

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

• Dòng đầu: \(N, M\) (\(2 \le N \le 100, 1 \le M \le 1000\)).
• \(M\) dòng tiếp: mỗi dòng \(u, v\) (\(1 \le u < v \le N\)), có cạnh từ \(u\) đến \(v\).

Định dạng đầu ra

• Một số nguyên là xác suất modulo \(10^9+7\).

Ví dụ

Input:

3 2
1 2
2 3

Output:

1

Giải thích: Chuột đi 1→2→3, chắc chắn đến N.

Ràng buộc

• 100% số điểm: \(N \le 100\).