34659번 - Last Celebration 다국어

To commemorate the end of a memorable era, the city is holding a Last Celebration. As a grand finale, a group of $N$ artists has been commissioned to create a final, collaborative mural on a massive city wall. The wall has a length of $D$ and is divided into $D$ sections, numbered from $1$ to $D$. Before they begin, the entire wall is primed with a base color, represented as color $0$.

Each artist $i$ is assigned a specific task: to paint the sections from $l_i$ to $r_i$ with their designated color $c_i$. As the artists work, some sections might be painted over multiple times. The final color of any section is determined by the last artist to paint it.

The quality of the final artwork is determined by its diversity. A block is defined as a maximal contiguous segment of the wall painted in a single color. The diversity of the wall is the total number of blocks.

The $N$ artists will complete their tasks in a random order. Each of the $N!$ possible permutations is equally likely. Your goal is to calculate the expected value of the wall's diversity after all artists are finished.

The first line contains two integers, $D$ and $N$ — the length of the wall and the number of artists.

The following $N$ lines each contain three integers, $l_i$, $r_i$, and $c_i$ — the range and color for the $i$-th artist.

Output the expected value of the wall's diversity. Since the expectation can be rational, output it modulo $998\,244\,353$. Formally, if the expectation equals $s/t$ in lowest terms, print $s\times t^{-1}\pmod{998\,244\,353}$, where $t^{-1}$ is the modular inverse of $t$ modulo $998\,244\,353$.

• $1 \le D \le 10^9$
• $1 \le N \le 2 \cdot 10^5$
• $1 \le l_i \le r_i \le D$
• $1 \le c_i \le N$