#P18946. [Mladen Manev 2021 A2] nksequences / 区间最大值约束计数

[Mladen Manev 2021 A2] nksequences / 区间最大值约束计数

区间最大值约束计数

统计长度为 NN 的整数序列 aa,满足 1≤ai≤K1\le a_i\le K,并满足给定的 MM 条约束:

max⁡lj≤i≤rjai=xj.\max_{l_j\le i\le r_j}a_i=x_j.

输出合法序列的数量,模 109+710^9+7。若约束互相矛盾,答案为零。

输入格式

第一行整数 N,M,KN,M,K。接下来 MM 行,每行三个整数 lj,rj,xjl_j,r_j,x_j。

输出格式

一个整数,表示方案数模 109+710^9+7。

数据范围

1≤N,M≤1051\le N,M\le10^5,1≤K≤1091\le K\le10^9,1≤lj≤rj≤N1\le l_j\le r_j\le N,1≤xj≤K1\le x_j\le K。

样例

5 3 4
1 2 1
1 3 2
3 5 4
7
3 3 3
1 2 2
2 3 3
1 3 1
0

来源与数据说明

2021 年 Dr. Mladen Manev,A2,原题名 nksequences。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。