The old linear algebra professor from a previous Moscow subregional problem keeps torturing his students with massive homework assignments. He came up with a way to describe a huge symmetric square matrix faster than dictating all its elements.

Professor chooses a positive integer $$$n$$$ and names $$$m$$$ ranges $$$[l_1, r_1], \ldots, [l_m, r_m]$$$ such that for all $$$i = 1, \ldots, m$$$ both $$$l_i$$$ and $$$r_i$$$ are integer, and $$$1 \leq l_i \leq r_i \leq n$$$. The $$$n \times n$$$ matrix $$$A$$$ is then constructed as follows: for any pair of indices $$$x, y$$$, the matrix element $$$A_{x, y}$$$ is equal to the number of indices $$$i$$$ ($$$1 \leq i \leq m$$$) such that both $$$x$$$ and $$$y$$$ belong to the range $$$[l_i, r_i]$$$. For example, for $$$n = 3$$$ and the list of ranges $$$[1, 2], [2, 3], [1, 2], [3, 3]$$$, the resulting matrix $$$A$$$ is $$$\begin{pmatrix}2 & 2 & 0 \\ 2 & 3 & 1 \\ 0 & 1 & 2\end{pmatrix}$$$.

Given $$$n$$$ and the list of ranges, professor then asks students to compute determinant of the resulting matrix $$$A$$$. Professor doesn't care for comparing huge numbers, so he asks for the answer to be computed modulo his favourite prime number $$$998\,244\,353$$$.

Professor may be cruel, but he is a reasonable teacher: he agrees there's little merit in exercise when writing down the problem is harder than actually solving it afterwards. Thus, in his assignments $$$m$$$ is never much greater than $$$n$$$, more precisely, $$$m \leq n + 300$$$.

After a few semesters in professor's class, you are very much done with his attitude and decided to write a program that will compute the answer for you.