题目描述

森林里有 $n$ 个林场，林场之间通过 $m$ 条单向高速公路连接，初始光头强在 $1$ 号林场。光头强想去 $n$ 号农场伐木，假设现在他在 $x$ 号林场，由于他没有导航，他会等概率地选择从 $x$ 出发的高速公路中的一条进行移动。如果没有任何从 $x$ 号林场出发的高速公路，他就只能留在原地了。光头强会一直走直到他无路可走。

请问光头强有多大的概率能够走到 $n$ 号城市。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $x,y(1≤x,y≤n)$ 描述一条从 $x$ 号城市到 $y$ 号城市的高速公路。

数据保证没有任何两条高速公路的 $x,y$ 是相同的。

输出格式

可以证明答案是分数，因此请输出答案 $mod\ 10^9+7$ 的结果。

Samples

3 2
1 2
1 3

500000004

数据范围

对于100%的数据，$2≤n≤100,1≤m≤1000$。