You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定一个 $n$ 个顶点 $m$ 条边的无向图，求其哈密顿路径条数。

本题中，一条哈密顿路径定义为：一个 $1$ 到 $n$ 的排列 $p_1,p_2, \cdots, p_n$ 满足，对于任意 $i(1 \le i \le n-1)$，无向边 $(p_i,p_{i+1})$ 存在。

输入格式

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

接下来 $m$ 行，每行两个正整数 $u,v$，表示图中的一条无向边 $(u,v)$。

输出格式

一行一个整数，表示图中哈密顿路径条数。由于结果可能过大，你只需要输出答案除以 $2$ 的余数即可。

样例输入

3 1
1 2

样例输出

0

样例解释

图不连通，故不存在哈密顿路径，所以哈密顿路径有 $0$ 条，$0$ 除以 $2$ 余数为 $0$。

子任务

对于所有数据，有 $1 \le n \le 30, 1 \le m \le 300, 1 \le u,v \le n$。

• 子任务 1 (11 分)：$n \le 5$
• 子任务 2 (45 分)：$n \le 17$
• 子任务 3 (14 分)：$n \le 24$
• 子任务 4 (30 分)：无特殊限制