题目描述

在一个国家，有 $n$ 座城市和 $m$ 条单向航线连接它们。城市的编号从 $0$ 到 $n-1$。其中，城市 $0$ 是你的起点 Syrjälä，城市 $n-1$ 是你的终点 Lehmälä。

你希望规划一条旅行路线，从 Syrjälä 出发，到 Lehmälä 结束，并且在途中恰好访问每一座城市一次（包括起点和终点城市）。

请你计算出有多少种不同的旅行路线方案。由于答案可能很大，请将结果对 $10^9 + 7$ 取模。

输入格式

第一行包含两个正整数 $n, m$，分别表示城市的数量和航线的数量。 接下来 $m$ 行，每行包含两个正整数 $a, b$，表示存在一条从城市 $a$ 到城市 $b$ 的单向航线。

输出格式

输出一行，包含一个整数，表示满足条件的路线总数。答案需要对 $10^9 + 7$ 取模。

4 6
0 1
0 2
1 2
2 1
1 3
2 3

2

数据规模与约定

数据范围

对于 $100\%$ 的数据，$2 \le n \le 20$，$1 \le m \le n^2$，$0 \le a, b < n$。