Vova 声称他发明了一种新型排序算法。按照 Vova 的说法，他的算法与众不同之处在于，它能够对任意长度为 $N$ 的排列进行排序，且对于任何排列，其执行的比较过程都是相同的。该算法总共进行 $M$ 次比较，其中第 $i$ 次比较发生在位置 $x_i$ 和 $y_i$ 的数字之间。如果在比较时，位置 $x_i$ 上的数字较大，则交换这两个数字。

Vanya 对 Vova 的发现持怀疑态度。他确信一定存在某些排列，使得 Vova 的排序算法无法将其按升序排列。请帮助 Vanya 确定这类排列的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示排列的大小和 Vova 排序算法中的比较次数。

接下来的 $M$ 行包含比较信息。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示被比较元素的位置。

$1 \le N \le 15$ $1 \le M \le 200$ $1 \le x_i, y_i \le N$

输出格式

输出一行，包含一个整数，即 Vova 的排序算法无法按升序排列的排列数量。

样例

输入格式 1

3 3
1 2
2 3
1 3

输出格式 1

2

说明

在第一个测试用例中，符合条件的排列为：$[3, 2, 1], [2, 3, 1]$。

输入格式 2

2 1
1 2

输出格式 2

0

说明

在第二个测试用例中，没有排列符合条件。

输入格式 3

2 1
2 1

输出格式 3

2

说明

在第三个测试用例中，符合条件的排列为：$[1, 2], [2, 1]$。