问题描述

有 $N$ 只兔子。兔子们从 $1$ 到 $N$ 编号。

这 $N$ 只兔子进行了徒步比赛。没有并列。在这种情况下，共有 $N!$ 种可能的顺序。

高桥君从 $M$ 个观众那里收集了信息。第 $i$ 个观众说，兔子 $x_i$ 在兔子 $y_i$ 之前到达终点。

请计算符合所有观众信息的可能顺序有多少种。

约束条件

• $2≤N≤16$
• $1≤M≤N(N-1)/2$
• $1≤x_i，y_i≤N$
• $x_i≠y_i$
• $(x_i，y_i)$ 对是互不相同的。
• 至少存在一个符合所有观众信息的顺序。

部分分

• 对于 $30$ 分的测试点，满足 $N≤8$。

输入

输入通过标准输入给出，具体格式如下。

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出

输出符合所有观众信息的可能顺序的数量。

示例输入1

3 2
2 1
2 3

示例输出1

2

有以下 $2$ 种可能的顺序：

• $(2，1，3)$
• $(2，3，1)$

示例输入2

5 5
1 2
2 3
3 5
1 4
4 5

示例输出2

3

有以下 $3$ 种可能的顺序：

• $(1，2，3，4，5)$
• $(1，2，4，3，5)$
• $(1，4，2，3，5)$

示例输入3

16 1
1 2

示例输出3

10461394944000

答案可能超出 $32$ 位整数范围。注意，此测试用例不在部分分的测试点中。