E. Nested Segmentstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA set $$$A$$$ consisting of pairwise distinct segments $$$[l, r]$$$ with integer endpoints is called good if $$$1\le l\le r\le n$$$, and for any pair of distinct segments $$$[l_i, r_i], [l_j, r_j]$$$ in $$$A$$$, exactly one of the following conditions holds: $$$r_i < l_j$$$ or $$$r_j < l_i$$$ (the segments do not intersect) $$$l_i \le l_j \le r_j \le r_i$$$ or $$$l_j \le l_i \le r_i \le r_j$$$ (one segment is fully contained within the other) You are given a good set $$$S$$$ consisting of $$$m$$$ pairwise distinct segments $$$[l_i, r_i]$$$ with integer endpoints. You want to add as many additional segments to the set $$$S$$$ as possible while ensuring that set $$$S$$$ remains good. Since this task is too easy, you need to determine the number of different ways to add the maximum number of additional segments to $$$S$$$, ensuring that the set remains good. Two ways are considered different if there exists a segment that is being added in one of the ways, but not in the other.Formally, you need to find the number of good sets $$$T$$$ of distinct segments, such that $$$S$$$ is a subset of $$$T$$$ and $$$T$$$ has the maximum possible size. Since the result might be very large, compute the answer modulo $$$998\,244\,353$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — the maximum right endpoint of the segments, and the size of $$$S$$$.The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the boundaries of the segments in set $$$S$$$.It is guaranteed that the given set $$$S$$$ is good, and the segments in set $$$S$$$ are pairwise distinct.It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output a single integer representing the number of different ways, modulo $$$998\,244\,353$$$, that you can add the maximum number of additional segments to set $$$S$$$ while ensuring that set $$$S$$$ remains good.ExampleInput61 02 31 12 21 25 21 32 34 11 16 21 34 62300 0Output1
1
2
5
4
187997613
NoteIn the first example, the only possible segment is $$$[1, 1]$$$, so $$$T = \{[1, 1]\}$$$ has the maximum size, and it is the only solution.In the second example, it is not possible to add any additional segments to set $$$S$$$. Hence, the only way to add segments to $$$S$$$ is adding nothing.In the third example, it is possible to add $$$7$$$ additional segments to $$$S$$$ while ensuring that the set remains good. It can be proven that adding more than $$$7$$$ additional segments to $$$S$$$ is not possible. There are exactly $$$2$$$ different ways to add these $$$7$$$ segments to $$$S$$$, and their respective sets $$$T$$$ are shown below: $$$\{[1, 1], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [5, 5]\}$$$ $$$\{[1, 1], [1, 3], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [4, 5], [5, 5]\}$$$. In the fourth example, there are exactly $$$5$$$ different ways to add a maximum of $$$6$$$ additional segments to $$$S$$$, and their respective sets $$$T$$$ are shown below: $$$\{[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4]\}$$$ $$$\{[1, 1], [1, 2], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]\}$$$ $$$\{[1, 1], [1, 3], [1, 4], [2, 2], [2, 3], [3, 3], [4, 4]\}$$$ $$$\{[1, 1], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [4, 4]\}$$$ $$$\{[1, 1], [1, 4], [2, 2], [2, 4], [3, 3], [3, 4], [4, 4]\}$$$