噶啦吗！

题目描述

Team Cherry 在设计《空洞骑士：丝之歌》的时候，设计了一场极长的连战，现在他们决定往里面添加一些怪物。

连战共有 $n$ 个波次，每个波次初始时都没有怪物。TC 总计会放入 $q$ 种怪物，为保持连战的连贯性，每种怪物只会连续地放在从第 $l_i$ 波到第 $r_i$ 波。每种怪物有一个实力值 $x_i$。所有怪物的实力值上限为 $V$。

灰机 Wiki 现在准备创作关于这一场连战的资料，它定义一个实力评估序列 $A$（长度为 $n$，且对于任意 $1 \le j \le n$，满足 $1 \le A_j \le V$ 的整数）是好的，当且仅当对于 $\forall i\in[1,q]$ 且 $\forall j\in[l_i,r_i]$，均有 $A_j\ge x_i$。

现在它想问你，有多少个实力评估序列 $A$ 是好的。由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

从文件 silksong.in 中读入数据。

第一行包含三个正整数 $n, q, V$，分别表示连战的波次数、怪物的种类数以及实力值的上限。 接下来 $q$ 行，每行包含三个正整数 $l_i, r_i, x_i$，表示第 $i$ 种怪物放置在第 $l_i$ 到第 $r_i$ 波次，且其实力值为 $x_i$。

输出格式

输出到文件 silksong.out 中。

输出一行一个整数，表示“好的”实力评估序列的数量对 $998244353$ 取模的结果。

样例 1

输入

3 2 5
1 2 2
2 3 3

输出

36

样例 1 解释 连战共有 $3$ 个波次，实力值上限 $V=5$。

• 第 $1$ 种怪物覆盖波次 $[1, 2]$，实力值为 $2$。
• 第 $2$ 种怪物覆盖波次 $[2, 3]$，实力值为 $3$。

对于实力评估序列 $A_1, A_2, A_3$：

• $A_1$ 必须 $\ge 2$，共有 $4$ 种。
• $A_2$ 必须 $\ge 3$，共有 $3$ 种。
• $A_3$ 必须 $\ge 3$，共有 $3$ 种。

易得总方案数为 $4 \times 3 \times 3 = 36$。

样例 2

见选手目录下的 silksong/silksong2.in 与 silksong/silksong2.ans。

这组样例的数据范围与测试点 $1$ 相同。

样例 3

见选手目录下的 silksong/silksong3.in 与 silksong/silksong3.ans。

这组样例的数据范围与测试点 $2 \sim 3$ 相同。

样例 4

见选手目录下的 silksong/silksong4.in 与 silksong/silksong4.ans。

这组样例的数据范围与测试点 $4 \sim 10$ 相同。

由于本题十分卡常，所以提供给选手一份快读代码

#define Tp template<typename T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){
    x=0;char c=getchar();bool f=0;
    for(;!isdigit(c);c=getchar())if(c=='-')f=1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    f&&(x=-x);
}

以及编译器优化

#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math,no-stack-protector")
#pragma GCC target("sse,sse2,avx,avx2,bmi,bmi2,lzcnt,popcnt,avx512vl,avx512f,tune=native")

数据范围与提示

对于所有测试数据，保证：$1 \le n \le 10^6$，$1 \le q \le 10^7$，$1 \le V \le 10^9$，$1 \le l_i \le r_i \le n$，$1 \le x_i \le V$。

提示： 对于某个波次 $j$，如果没有怪物覆盖该波次，则 $A_j$ 可以是 $1$ 到 $V$ 之间的任意整数。