There are \(N\) cities and \(M\) directed roads connecting them. The king is at city \(1\) and his queen is at city \(N\).

He needs to find the number of ways to reach the queen. The cities are connected in a way that they don't form directed cycles.

Input Format:

The first input line has two integers \(N\) and \(M\)
Then there are \(M\) lines describing the roads. Each line has two integers \(a\) and \(b\) i.e there is a directed road from city \(a\) to city \(b\)

Output Format:

 Print the number of ways modulo \(10^9 + 7\)

Constraints:

\(1 \leq N \leq 2*10^5 \\ 1 \leq M \leq 4*10^5 \\ 1 \leq a,b \leq N\)