H-Permutation Counting_MINIEYE杯第十六届华中科技大学程序设计邀请赛

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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  and , indicating the length of the permutation and the number of constraints.

The -th of the following  lines contains two integers  and  indicating the constraint that . It is guaranteed that all  are distinct.

输出描述:

Output an integer indicating the number of permutations satisfying the conditions modulo .

示例1

输入

复制

3 1
1 2

输出

复制

说明

In the first sample, all valid permutations are  and , so the answer is .

示例2

输入

复制

3 2
1 2
2 3

输出

复制

示例3

输入

复制

3 2
1 2
2 1

输出

复制

示例4

输入

复制

输出

复制