8551: Yet Another Easy Permutation Count Problem

Silver187 likes Permutation. For a permutation $P$ of length $n$, a position $x(2\le x\le n-1)$ is a good position if and only if P_xPi<Px, andPx>Px+1. In particular:

1. position $1$ is a good position if and only if P1>P2 and $n\ge 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 - 1in 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≤106), $(0\le m\le 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≤107.

2
3 1
1 2
7 5
4 5
2 2
6 7
3 3
1 4

3
13