为了纪念一个难忘时代的结束，这座城市正在举行一场“最后的庆典”（Last Celebration）。作为压轴戏，一个由 $N$ 位艺术家组成的团队被委托在一面巨大的城墙上创作一幅最终的合作壁画。城墙的长度为 $D$，并被划分为 $D$ 个部分，编号从 $1$ 到 $D$。在他们开始之前，整面墙都涂上了底色，用颜色 $0$ 表示。

每位艺术家 $i$ 被分配了一个特定的任务：用他们指定的颜色 $c_i$ 绘制从 $l_i$ 到 $r_i$ 的区域。在艺术家们工作的过程中，某些区域可能会被多次覆盖。任何区域的最终颜色由最后绘制它的艺术家决定。

最终艺术品的质量由其多样性决定。一个“块”（block）被定义为涂有单一颜色的极大连续墙面段。墙面的多样性是块的总数。

这 $N$ 位艺术家将以随机的顺序完成他们的任务。$N!$ 种可能的排列中的每一种都是等概率的。你的目标是计算所有艺术家完成工作后，墙面多样性的期望值。

输入格式

第一行包含两个整数 $D$ 和 $N$ —— 墙的长度和艺术家的数量。

接下来的 $N$ 行，每行包含三个整数 $l_i$、$r_i$ 和 $c_i$ —— 第 $i$ 位艺术家的绘制区间和颜色。

输出格式

输出墙面多样性的期望值。由于期望值可能是有理数，请输出其模 $998\,244\,353$ 的值。具体来说，如果最简分数形式的期望值为 $s/t$，输出 $s \times t^{-1} \pmod{998\,244\,353}$，其中 $t^{-1}$ 是 $t$ 模 $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$

样例

输入样例 1

5 2
1 4 1
2 3 2

输出样例 1

3

输入样例 2

6 3
2 3 1
4 5 1
1 6 2

输出样例 2

332748120

输入样例 3

1000000000 9
1 2 1
11 22 1
111 222 1
1111 2222 1
11111 22222 1
111111 222222 1
1111111 2222222 1
11111111 22222222 1
111111111 222222222 1

输出样例 3

18

输入样例 4

4 10
1 1 1
1 2 2
1 3 3
1 4 4
2 2 5
2 3 6
2 4 7
3 3 8
3 4 9
4 4 10

输出样例 4

356515843