你受聘监督一个新游乐园的项目。该公园有一个特殊的噱头：定向滑道，可以让游客快速且有趣地从一个景点到达另一个景点。

公园业主给了你当前的项目：一份计划中的景点列表，以及一份应该在它们之间建造的滑道列表。然而，作为一个商人，他随口设想了一些不可能的事情：例如，他规划了一条从鬼屋到过山车的滑道，另一条从过山车到跳楼机的滑道，以及第三条从跳楼机到鬼屋的滑道。由于滑道只能下坡，很明显这就是一个问题。在建造公园时，你不能忽视物理定律，因此你必须要求更改项目。也许他会接受将跳楼机和鬼屋之间的滑道反向？

形式化地： 项目是景点列表和定向滑道列表。每条滑道从一个景点开始，在另一个景点结束。 方案是通过反转某些滑道（可能是不反转或全部反转）的方向从项目中获得的。 如果存在一种为每个景点分配高度的方法，使得每条滑道都向下，则该方案是合法的。 方案的代价是其被反转方向的滑道数量。

对于给定的项目，找出并报告所有合法方案的代价之和。由于这个数字可能很大，请输出其对 $998, 244, 353$ 取模的结果。

输入格式

第一行包含两个空格分隔的整数 $n, m$ ($1 \le n \le 18, 0 \le m \le n(n - 1)/2$)，分别表示景点的数量和滑道的数量。景点编号为 $1$ 到 $n$。

接下来 $m$ 行，第 $i$ 行包含两个空格分隔的整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，表示一条从 $a_i$ 到 $b_i$ 的滑道。

你可以假设： 没有自环。（对于每个 $i$：$a_i \neq b_i$。） 没有重复的滑道。（对于所有 $i \neq j$：$a_i \neq a_j$ 或 $b_i \neq b_j$。） * 没有一对景点在两个方向上都有连接。（无序对 $\{a_i, b_i\}$ 是不同的。）

输出格式

输出一行，包含一个整数，即所有合法方案的代价之和对 $998, 244, 353$ 取模的结果。

子任务

子任务 1 (7 分)：$n \le 3$ 子任务 2 (12 分)：$n \le 6$ 子任务 3 (23 分)：$n \le 10$ 子任务 4 (21 分)：$n \le 15$ 子任务 5 (37 分)：无附加限制

样例

样例输入 1

2 1
1 2

样例输出 1

1

样例输入 2

3 3
1 2
2 3
1 3

样例输出 2

9

说明

在第一个样例中，有两个方案： 滑道方向未翻转。该方案代价为 0。 滑道方向已翻转。该方案代价为 1。

由于两个方案都有效，答案为 $0 + 1 = 1$。

在第二个样例中，有八个方案，滑道方向如下： $1 \to 2, 2 \to 3, 1 \to 3$ (代价 0) $1 \to 2, 2 \to 3, 3 \to 1$ (代价 1) $1 \to 2, 3 \to 2, 1 \to 3$ (代价 1) $1 \to 2, 3 \to 2, 3 \to 1$ (代价 2) $2 \to 1, 2 \to 3, 1 \to 3$ (代价 1) $2 \to 1, 2 \to 3, 3 \to 1$ (代价 2) $2 \to 1, 3 \to 2, 1 \to 3$ (代价 2) $2 \to 1, 3 \to 2, 3 \to 1$ (代价 3)

第二个方案不合法，因为存在滑道序列 $1 \to 2 \to 3 \to 1$。这意味着景点 1 必须严格高于自身，这显然是不可能的。同样，第七个方案也不合法。因此答案为 $0 + 1 + 2 + 1 + 2 + 3 = 9$。