409778: GYM103741 H Permutation Counting

Memory Limit:512 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Permutation Countingtime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

ExamplesInput
3 1
1 2
Output
3 
Input
3 2
1 2
2 3
Output
1 
Input
3 2
1 2
2 1
Output
0 
Input
10 7
1 2
3 2
5 4
7 8
2 6
4 6
8 6
Output
37800 
Note

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

Source/Category

加入题单

上一题 下一题 算法标签: