A permutation on the numbers $1, 2, \dots, n$ is a linear ordering of the numbers. For example, there are $6$ permutations of the numbers $1, 2, 3$. They are $123$, $132$, $213$, $231$, $312$ and $321$. Another way to think of it is removing $n$ disks numbered $1$ to $n$ from a bag (without replacement) and recording the order in which they were drawn out.</p>

Mathematicians (and other smart people) write down that there are $n! = n \times (n-1) \dots 3 \times 2 \times 1$ permutations of the numbers $1, \dots, n$. We call this "$n$ factorial."

For this problem, you will be given an integer $n$ $(1 \le n \le 9)$ and a series of $k$ $(k \ge 0)$ constraints on the ordering of the numbers. That is, you will be given $k$ pairs $(x,y)$ indicating that $x$ must come before $y$ in the permutation.

You are to output the number of permutations which satisfy all constraints.

입력 형식

Your input will be $k + 2$ lines. The first line will contain the number $n$. The second line will contain the integer $k$, indicating the number of constraints. The remaining $k$ lines will be pairs of distinct integers which are in the range $1, \dots, n$.

출력 형식

Your output will be one integer, indicating the number of permutations of $1, \dots, n$ which satisfy the $k$ constraints.

예제 입력 1

3
2
1 2
2 3

예제 출력 1

1

예제 입력 2

4
2
1 2
2 1

예제 출력 2

0

예제 입력 3

4
2
1 2
2 3

예제 출력 3

4