题目描述

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

请问光头强走到第 $n$ 个林场时，经过的高速公路数量的期望值是多少？

输入格式

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

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

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

数据保证所有林场都可以到 $n$ 号林场。

输出格式

一行一个数表示光头强期望经过多少条高速公路能够走到 $n$ 号林场。由于答案是分数，请输出答案 $mod\ 10^9+7$。

Samples

3 3
1 2
1 3
2 3

500000005

数据范围

对于100%的数据，$2≤n≤100,1≤m≤n×(n-1)$。