该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

高考结束，大家各奔东西。离开自己的家乡，前往一所陌生的大学，在这个内卷的时代，所有人都在和你说要好好努力，要有上进心，专心学习不要乱搞其他的东西。在埋头苦学的日日夜夜中，最珍贵的东西却在恍惚间悄然远去。曾经的友人们是否还常联系，父母的身体是否还安好，青涩的爱情是否经得住时间的考验？成长的路上不只有成绩，还有这一路的风景，珍惜当下的美好，为了自己与身边的重要之人，然后拼尽全力去搏吧。

题目描述

你的人生节点有 $n$ 个时空，编号从 $1$ 到 $n$ ，为了想次想起人生中那些重要的人，Yue_chen帮你建立了 $m$ 条时空间的单向通道，每天你可以选择走一条之前从未选择过得的通道进行回忆，之后，你将从原本的时空前往通道另一侧的时空。在任意一天的开始时，你可以选择结束回忆。Yue_chen想知道，如果从时空 $1$ 出发，你会有多少种不同的回忆方式。

输入格式

第一行两个正整数 $n(1 \le n \le 10^6)$，$m (0 \le m \le 8)$，$n$表示时空的个数, $m$表示通道的个数。 第二行至第m+1行每行两个正整数 $u(1 \le u \le n),v(1 \le v \le n)$，表示时空 $u$ 到时空 $v$ 有一条序号为 $i(i$ 定义为行数 $-1)$ 单向通道。

输出格式

输出一个整数表示有多少种不同的回忆方式。(两种回忆方式不同，当且仅当第 $x$ 天选择的通道的序号不相同)

输入输出样例

输入 #1

2 4
1 2
1 2
2 1
2 1

输出 #1

15

输入 #2

100 0

输出 #2

1