You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 终于迎来了自己的大学生活最后的时刻，他决定用自己的积蓄来一场说走就走的毕业旅行，并且不玩的开心不上班。然而，他很快就发现这个决定并非那么简单。由于是暑假，假期人多，他既不想错过旅行的最佳时期，又不想在人群中挣扎，预测旅游热门城市的拥挤时段，就像是一道难题摆在他的面前。

在浏览了一堆旅游网站和社交媒体后，小 Z 发现了一个可以帮助他制定完美旅行计划的手机应用程序。这个应用程序基于人工智能算法，预测了旅游热门城市在不同时段的拥挤程度，为旅行者提供了精准的建议。

小 Z 选出来想要旅行的 $n$ 个城市（城市编号为 $1 \sim n$），由于现在交通非常发达，可以认为这些城市之间互相都可以连通，小 Z 每天只会在一个不拥挤的城市停留，第二天他可以选择去任意一个不拥挤的城市并一整天留在那里（当然，也可以继续留在原本的城市，如果原本的城市不拥挤的话），然后他选择这 $n$ 个城市，出发日期 $S$ 和返回日期 $T$（可以理解为小 Z 的旅游日期为第 $[S,T]$ 天），应用程序根据这些信息，开始生成一份详细的报告，其中包括了 $m$ 条信息，每条信息包含三个数 $x$，$l$，$r$，在第 $[l,r]$ 天是小 Z 选出来的第 $x$ 个城市是拥挤的，通过这份报告，小 Z 了解到了不同城市的拥挤时段，并制定了避开高峰期的旅行计划。有了这个应用程序的帮助，小 Z 可以尝试制定一份完美的旅行计划，开启了一场避开人群的毕业旅行。

由于小 Z 非常懒，不逛完所有城市也无所谓，现在小 Z 想知道他能够实现错峰毕业旅行的方案有多少种（注意小 Z 可以从任意一个城市开始毕业旅行，我们认为两个方案是不同的当且仅当至少存在一天两个方案小 Z 所处的城市不同），由于这个方案数很大，他只想知道方案数对 $10^9+7$ 取模以后的结果 。

输入格式

从 travel.in 文件读入数据。

第一行输入的四个整数 $n$，$m$，$S$，$T$，含义与上文描述一致。

接下来的 $m$ 行分别包含三个数字 $x$，$l$，$r$，表示第 $x$ 个城市在第 $[l,r]$ 天是拥挤的 ，其中 $1 \le x\le n$，$S \le l,r \le T$ ，需要注意的是不同信息的 $x$ 可能会相同，但拥挤的时间段 $[l,r]$ 不会与之前给出的 $x$ 城市的拥挤时间有交集。

输出格式

输出到 travel.out 文件。

一行，一个整数，表示小 Z 错峰毕业旅行的方案数对 $10^9+7$ 取模以后的结果。

样例

5 4 2 6
1 2 2
2 3 6
4 4 5
5 2 6

108

样例4

此样例满足 $50\%$ 数据点范围限制。

点击链接 ex_travel2.in 和 ex_travel2.out 下载大样例 2 的输入数据和输出数据。

样例5

此样例满足 $100\%$ 数据点范围限制。

点击链接 ex_travel3.in 和 ex_travel3.out 下载大样例 3 的输入数据和输出数据。

数据范围

对于 $45\%$ 数据，$1 \le n \le 5000$，$1\le m \le 5000$，$0 \le S \le T \le 10^9$，且 $T-S \le 5000$

对于 $100\%$ 数据，$1 \le n \le 5000$，$1\le m \le 10^6$，$0 \le S \le T \le 10^9$，且 $T-S \le 10^9$ 。