Hamiltonian Flights

题目描述

有 n 个城市和 m 条航线连接。你想从 Syrjälä 前往 Lehmälä，且恰好访问每个城市一次。共有多少种可能的路径？

输入格式

第一行输入包含两个整数 n 和 m：城市数和航线数。城市编号为 1,2,$\dots$,n。城市 1 为 Syrjälä，城市 n 为 Lehmälä。 接下来有 m 行描述航线。每行有两个整数 a 和 b：存在一条从城市 a 到城市 b 的航班。所有航班均为单向航班。

输出格式

输出一个整数：路径数量对 $10^9+7$ 取模的结果。

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

2

提示

$2 \le n \le 20$ $1 \le m \le n^2$ $1 \le a,b \le n$

标签: CSES1690|图论

来源

CSES1690|图论