题目描述

给定有向图 $G = (V,E)$ ，其中 $V$ 为点集， $E$ 为边集。设 $G$ 包含 $n$ 个结点，用正整数 $1,2,··· ,n$ 表示，即 $V = \{1,2,··· ,n\}$ 。

对于 $V$ 的任意非空子集 $S\subseteq V$ ，如果 $S$ 中任意点的任意后继均属于 $S$ ，即对任意 $u \in S$ 及 $u$ 的出边 $(u,v) \in E$ 均满足 $v \in S$ ，则称 $S$ 是 $G$ 的一个闭合子图。

你的任务是，求出有多少个 $G$ 的非空闭合子图 $S$ ，满足 $S$ 中的点编号是连续的。连续的定义：对任意整数 $i < k < j$ ，若 $i, j \in S$ ，则 $k \in S$ 。

输入格式

第一行两个整数 $n,m$ ，表示图 $G$ 的结点数和边数。

接下来 $m$ 行，每行两个正整数 $u_i$ , $v_i$ ，表示有一条从点 $u_i$ 到点 $v_i$ 的边 $(u_i ,v_i ) \in E$ 。

图 $G$ 可能包含重边和自环。

输出共一行，包含一个整数，表示所求的闭合子图的个数。

由于答案可能很大，所以这里要求输出答案对 $10^9+7$ 取模的结果。

见附件: graph2.in

见附件: graph2.out