6577: Yet Another Easy Permutation Count Problem
内存限制：256 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Silver187 likes Permutation. For a permutation P of length n, a position x(2≤x≤n−1) is a good position if and only if ∀1≤i≤x−1,Pi<Px, and Px>Px+1. In particular:
1. position 1 is a good position if and only if P1>P2 and n≥2.
2. position n can never be a good position.
Silver187 wants to calculate the beauty value of a permutation P of length n. He defines a number S, initially S=0. Silver187 will repeat the following operations for the permutation P until the permutation P is in ascending order.
1. Add to S the number of good positions in the current permutaion P.
2. Do a bubble sort on the permutation P(For each i from 1 to n−1 in order, if Pi > Pi+1, swap Pi, Pi+1).
S is the beautiful value of the permutation P.
Silver187 gives you two numbers n and m. There are m constraints. Every constraint will give x and y, which means the inital number of position x is y. Find the sum of the beauty values of all permutations that satisfy all constraints modulo 998244353.
1. position 1 is a good position if and only if P1>P2 and n≥2.
2. position n can never be a good position.
Silver187 wants to calculate the beauty value of a permutation P of length n. He defines a number S, initially S=0. Silver187 will repeat the following operations for the permutation P until the permutation P is in ascending order.
1. Add to S the number of good positions in the current permutaion P.
2. Do a bubble sort on the permutation P(For each i from 1 to n−1 in order, if Pi > Pi+1, swap Pi, Pi+1).
S is the beautiful value of the permutation P.
Silver187 gives you two numbers n and m. There are m constraints. Every constraint will give x and y, which means the inital number of position x is y. Find the sum of the beauty values of all permutations that satisfy all constraints modulo 998244353.
输入
The first line has one integer T(1≤T≤100), indicating there are T test cases.
In each case:
The first line contains two integers n(1≤n≤10^6), m(0≤m≤n)---the length of the permutation and the number of constraints.
The i-th line of the next m line contains two integers---the i-th constraint.
It is guaranteed that there is at least one permutation that satisfies all constraints.
Input guarantee 1≤∑m≤∑n≤10^7.
In each case:
The first line contains two integers n(1≤n≤10^6), m(0≤m≤n)---the length of the permutation and the number of constraints.
The i-th line of the next m line contains two integers---the i-th constraint.
It is guaranteed that there is at least one permutation that satisfies all constraints.
Input guarantee 1≤∑m≤∑n≤10^7.
输出
In each case, output a single integer---the sum of the beautiful values of all permutations that satisfy the constraints modulo 998244353.
样例输入 复制
2
3 1
1 2
7 5
4 5
2 2
6 7
3 3
1 4样例输出 复制
3
13