题目描述
寒冬将至,FIS滑雪世界杯正在火热进行,选手们将参加本赛季中的举办的若干场比赛,以获取积分获得奥运会资格。作为滑雪比赛的忠实观众,小 Z 自然不打算错过任何一场比赛。
在小 Z 的世界中,世界杯的赛制与现实有较大的不同:本赛季共有 m 个比赛日,将依次举行 m 场比赛,有 n 名选手参加,第 i 名选手在之前的赛季中已经有了 wi 的积分,由于身体原因,会在第 li 个比赛日抵达比赛现场,第 ri 个比赛日离开,参加第 li∼ri 场比赛。每场比赛如果有至少一人参加,就会在这些选手间进行竞争,选出唯一的胜者,胜者将获得 1 点积分。
特别地,为了保证公平,不让一些选手参与过多的比赛,对于任意两名选手 i,j,如果 i 比 j 先抵达现场,则不能比 j 更晚离开。即 ∀1≤i,j≤n,li<lj 则 ri≤rj。
不幸的是,小 Z 最喜欢的一名选手 UFT 由于身体原因将缺席本赛季所有的比赛(UFT 不算在那 n 名选手中,可以看作共有 n+1 名选手进行排名),小 Z 想知道 UFT 还有没有出线晋级奥运会的理论可能。UFT 在以往的赛季中获得了积分 v,由于不确定奥运会名额的数量,小 Z 想向你询问本赛季结束后所有的不同积分情况中,UFT 的排名最高为多少(定义一名选手的排名为分数比他高的选手数量 +1),设这个最小值为 mn,你需要输出 n+1−mn 的大小(即分数不高于 v 的选手数量)。由于积分相同需要考虑选手历史战绩,所以小 Z 还想要额外知道:所以可以达到的,满足 UFT 排名为 mn 的不同最终积分情况中,积分不高于 UFT 的选手集合有多少种不同的可能。答案关于 109+7 取模。
输入格式
第一行四个整数 n,m,v,tp。n,m,v 参见题目描述, tp 为询问类型满足 tp∈{0,1},当 tp=0 时你只需要输出第一问答案,tp=1 时则需要输出两问的答案。
接下来 n 行,第 i 行三个正整数 wi,li,ri。
输出格式
一行一个或两个整数表示答案,答案之间用空格隔开。
样例数据
input
7 7 2 1 1 1 1 1 2 3 2 3 4 1 4 4 2 4 5 1 5 6 2 5 7
output
5 2
样例解释
可能 1:比赛胜者依次为 1,2,3,3,7,7,7,选手 1,2,4,5,6 分数 ≤2。
可能 2:比赛胜者依次为 1,2,2,4,7,7,7,选手 1,3,4,5,6 分数 ≤2。
数据规模与约定
对于所有测试数据,有 1≤n,m≤2×105,0≤wi,v≤1×109,1≤li≤ri≤m,0≤tp≤1。 且 ∀1≤i,j≤n,i≠j,若 li<lj 则 ri≤rj。
subtask 1(5%): n,m≤8。
subtask 2(5%): n,m≤15。
subtask 3(20%): n,m≤20。
subtask 4(10%): n,m≤2000,tp=0。
subtask 5(20%): tp=0。
subtask 6(20%): n,m≤2000。
subtask 7(20%): 无特殊限制。
时间限制:1s
空间限制:256MB