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$