博弈论是计算机科学中一个有趣的课题。

SG 函数是博弈论中的一个重要概念。给定一个顶点集为 $V_1$、有向边集为 $E_1$ 的有向无环图 $G_1$，对于每个顶点 $u \in V_1$，其 SG 函数 $sg(u)$ 定义为：

$$sg(u) = \text{mex}(\{sg(v) \mid (u, v) \in E_1\})$$

其中，对于给定的非负整数集合 $S$，$\text{mex}(S)$ 定义为不属于 $S$ 的最小非负整数。

今天，Rikka 想要将 SG 函数推广到无向图上。给定一个顶点集为 $V$、无向边集为 $E$ 的无向图 $G$，函数 $f$ 是 $G$ 上的一个有效 SG 函数，当且仅当：

• 对于每个顶点 $u \in V$，$f(u)$ 是一个非负整数；
• 对于每个顶点 $u \in V$，$f(u) = \text{mex}(\{f(v) \mid (u, v) \in E\})$。

根据这个定义，一个图可能存在多个有效的 SG 函数。因此，Rikka 想要进一步探究这些有效 SG 函数之间是否存在联系。作为第一步，你的任务是计算给定无向图 $G$ 的有效 SG 函数的数量。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 17, 0 \le m \le \frac{n(n-1)}{2}$)，分别表示图的顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示图中的一条边。

题目保证图中没有自环和重边。

输出格式

输出一行，包含一个整数，表示有效 SG 函数的数量。

样例

样例输入 1

5 4
1 2
2 3
3 4
4 5

样例输出 1

6

说明

为简便起见，我们使用列表 $[f(1), \dots, f(n)]$ 来表示函数 $f$。

对于样例输入，共有 6 个有效的 SG 函数：

• $[0, 1, 0, 1, 0], [0, 1, 2, 0, 1], [0, 2, 1, 0, 1], [1, 0, 1, 0, 1], [1, 0, 1, 2, 0]$ 以及 $[1, 0, 2, 1, 0]$。