제약이 있는 순열

$1, 2, \dots, n$ 의 순열이란 이 수들을 일렬로 나열한 것을 말합니다. 예를 들어 $1, 2, 3$ 의 순열은 $6$ 가지이며, $123$, $132$, $213$, $231$, $312$, $321$ 입니다. 다르게 생각하면, $1$ 부터 $n$ 까지 번호가 적힌 $n$ 개의 원반을 주머니에서 (다시 넣지 않고) 하나씩 꺼내어 꺼낸 순서를 기록하는 것과 같습니다.

$1, \dots, n$ 의 순열의 개수는 $n! = n \times (n-1) \dots 3 \times 2 \times 1$ 로 나타내며, 이를 "$n$ 팩토리얼"이라고 부릅니다.

이 문제에서는 정수 $n$ $(1 \le n \le 9)$ 과 수들의 순서에 대한 $k$ $(k \ge 0)$ 개의 제약이 주어집니다. 각 제약은 순열에서 $x$ 가 $y$ 보다 반드시 앞에 와야 함을 의미하는 쌍 $(x, y)$ 로 주어집니다.

모든 제약을 만족하는 순열의 개수를 출력하세요.

입력은 $k + 2$ 개의 줄로 이루어집니다. 첫째 줄에는 정수 $n$ 이 주어집니다. 둘째 줄에는 제약의 개수를 나타내는 정수 $k$ 가 주어집니다. 이어지는 $k$ 개의 줄에는 각각 $1, \dots, n$ 범위에 속하는 서로 다른 두 정수 $x$ 와 $y$ 가 주어지며, 이는 $x$ 가 $y$ 보다 앞에 와야 함을 의미합니다.

$k$ 개의 제약을 모두 만족하는 $1, \dots, n$ 의 순열의 개수를 정수 하나로 출력합니다.