题目描述

寒冬将至，FIS滑雪世界杯正在火热进行，选手们将参加本赛季中的举办的若干场比赛，以获取积分获得奥运会资格。作为滑雪比赛的忠实观众，小 Z 自然不打算错过任何一场比赛。

在小 Z 的世界中，世界杯的赛制与现实有较大的不同：本赛季共有 $m$ 个比赛日，将依次举行 $m$ 场比赛，有 $n$ 名选手参加，第 $i$ 名选手在之前的赛季中已经有了 $w_i$ 的积分，由于身体原因，会在第 $l_i$ 个比赛日抵达比赛现场，第 $r_i$ 个比赛日离开，参加第 $l_i\sim r_i$ 场比赛。每场比赛如果有至少一人参加，就会在这些选手间进行竞争，选出唯一的胜者，胜者将获得 $1$ 点积分。

特别地，为了保证公平，不让一些选手参与过多的比赛，对于任意两名选手 $i,j$，如果 $i$ 比 $j$ 先抵达现场，则不能比 $j$ 更晚离开。即 $\forall 1\le i,j\le n$，$l_i < l_j$ 则 $r_i\le r_j$。

不幸的是，小 Z 最喜欢的一名选手 UFT 由于身体原因将缺席本赛季所有的比赛（UFT 不算在那 $n$ 名选手中，可以看作共有 $n+1$ 名选手进行排名）,小 Z 想知道 UFT 还有没有出线晋级奥运会的理论可能。UFT 在以往的赛季中获得了积分 $v$，由于不确定奥运会名额的数量，小 Z 想向你询问本赛季结束后所有的不同积分情况中，UFT 的排名最高为多少（定义一名选手的排名为分数比他高的选手数量 $+1$），设这个最小值为 $mn$，你需要输出 $n+1-mn$ 的大小（即分数不高于 $v$ 的选手数量）。由于积分相同需要考虑选手历史战绩，所以小 Z 还想要额外知道：所以可以达到的，满足 UFT 排名为 $mn$ 的不同最终积分情况中，积分不高于 UFT 的选手集合有多少种不同的可能。答案关于 $10^9+7$ 取模。

输入格式

第一行四个整数 $n,m,v,tp$。$n,m,v$ 参见题目描述， $tp$ 为询问类型满足 $tp\in \{0,1\}$，当 $tp=0$ 时你只需要输出第一问答案，$tp=1$ 时则需要输出两问的答案。

接下来 $n$ 行，第 $i$ 行三个正整数 $w_i,l_i,r_i$。

输出格式

一行一个或两个整数表示答案，答案之间用空格隔开。

样例数据

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$ 分数 $\le 2$。

可能 $2$：比赛胜者依次为 $1,2,2,4,7,7,7$，选手 $1,3,4,5,6$ 分数 $\le 2$。

数据规模与约定

对于所有测试数据，有 $1\le n,m\le 2\times 10^5,0\le w_i,v\le 1\times 10^9,1\le l_i\le r_i\le m,0\le tp\le 1$。 且 $\forall 1\le i,j\le n,i\not =j$，若 $l_i< l_j$ 则 $r_i\le r_j$。

subtask $1$($5\%$): $n,m\le 8$。

subtask $2$($5\%$): $n,m\le 15$。

subtask $3$($20\%$): $n,m\le 20$。

subtask $4$($10\%$): $n,m\le 2000,tp=0$。

subtask $5$($20\%$): $tp=0$。

subtask $6$($20\%$): $n,m\le 2000$。

subtask $7$($20\%$): 无特殊限制。

时间限制：$1\text{s}$

空间限制：$256\text{MB}$