Constrained Permutations

A permutation of the numbers $1, 2, \dots, n$ is a linear ordering of those numbers. For example, there are $6$ permutations of $1, 2, 3$: they are $123$, $132$, $213$, $231$, $312$, and $321$. Another way to think of it is drawing $n$ disks numbered $1$ to $n$ from a bag (without replacement) and recording the order in which they come out.

The number of permutations of $1, \dots, n$ is written $n! = n \times (n-1) \dots 3 \times 2 \times 1$, which we call "$n$ factorial."

In this problem you are given an integer $n$ $(1 \le n \le 9)$ and a series of $k$ $(k \ge 0)$ constraints on the ordering of the numbers. Each constraint is a pair $(x, y)$ meaning that $x$ must come before $y$ in the permutation.

Output the number of permutations that satisfy all of the constraints.

The input consists of $k + 2$ lines. The first line contains the integer $n$. The second line contains the integer $k$, the number of constraints. Each of the following $k$ lines contains two distinct integers $x$ and $y$ in the range $1, \dots, n$, meaning that $x$ must come before $y$.

Output a single integer: the number of permutations of $1, \dots, n$ that satisfy all $k$ constraints.