## Day 2, Problem 1: Constrained Permutations

A permutation on the numbers 1,2,...,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.

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

For this problem, you will be given an integer n (1 ≤ n ≤ 9) and a series of k (k ≥ 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.

### Input

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,...,n.

### Output

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

```3
2
1 2
2 3
```

```1
```

```4
2
1 2
2 1
```

```0
```

```4
2
1 2
2 3
```

### Sample Output 3

```4
```

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M