409778: GYM103741 H Permutation Counting

You are given an integer $$$n$$$, and $$$m$$$ pairs of integers $$$(x_i,y_i)\ (1\le i\le m)$$$ with distinct $$$x_i$$$, i.e. $$$x_i\neq x_j$$$ for all $$$i\neq j$$$. You need to find the number of permutation $$$p$$$ of length $$$n$$$ satisfying $$$p_{x_i} < p_{y_i}$$$ for all $$$i$$$. Since the number might be too large, you only need to output the answer modulo $$$998\,244\,353$$$.

Recall that a permutation of length $$$n$$$ is a sequence of length $$$n$$$ and contains $$$1,2,\dots, n$$$ exactly once. For instance, $$$\{1,2,3\}$$$ and $$$\{3,1,2\}$$$ are permutations while $$$\{1,2,4\}$$$ and $$$\{1,2,2\}$$$ are not.

The first line contains two integers $$$n\ (1 \leq n \leq 2\cdot 10^6)$$$ and $$$m\ (0 \leq m \leq n)$$$, indicating the length of the permutation and the number of constraints.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i\ (1\le x_i\le n)$$$ and $$$y_i\ (1\le y_i\le n, x_i\neq y_i)$$$ indicating the constraint that $$$p_{x_i}<p_{y_i}$$$.

Output an integer indicating the number of permutations satisfying the conditions modulo $$$998\,244\,353$$$.

3 1
1 2

3 

3 2
1 2
2 3

1 

3 2
1 2
2 1

0 

10 7
1 2
3 2
5 4
7 8
2 6
4 6
8 6

37800 

In the first sample, all valid permutations are $$$\{1,2,3\},\{1,3,2\}$$$ and $$$\{2,3,1\}$$$, so the answer is $$$3$$$.