题目描述

给定一个有 $n$ 个顶点、$m$ 条有向边的图，顶点编号为 $0,1,\ldots,n-1$。

你需要完成如下操作：

1. 选择一个整数 $k$，满足 $1\le k\le n$；
2. 给每个顶点标上 $1$ 到 $k$ 之间的一个整数；
3. 对每个 $j=1,2,\ldots,k-1$，都必须存在至少一条有向边，它的起点标号为 $j$，终点标号为 $j+1$。

只要存在某个顶点的最终标号不同，就认为两种方案不同。求所有可能的标号方案总数，对 $10^9+7$ 取模。

输入格式

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

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示存在一条从 $a_i$ 指向 $b_i$ 的有向边。

输出格式

输出一个整数，表示合法标号方案数对 $10^9+7$ 取模的结果。

数据范围

• $1\le n\le15$；
• $0\le m\le n(n-1)$；
• $0\le a_i,b_i<n$ 且 $a_i\ne b_i$；
• 所有有序对 $(a_i,b_i)$ 两两不同。

样例 1

3 3
0 1
1 2
2 0

10

样例 2

5 3
0 1
1 2
2 0

52