题面描述

众所周知，磊爷是个很能干的工具人，学长学姐学弟学妹还有同学们都很喜欢。

现在，学长将把大一分队的任务交给了磊爷。由于要分队而且大一的水平近似相等，于是我们就可以尽情的排列组合~

众所周知，ACM 是一个三人游戏，所以最好能找到三名队友一起来玩!

但是由于各种原因，每位同学可以训练的时间并不完全相同。现在已知有 $n$ 种训练计划，每种训练计划从 $l_i$ 开始到 $r_i$ 结束，选择这个训练计划的有 $p_i$ 人，每位同学只会选择其中一种。

试问，根据他们选择的，可以组建出多少个不同的队伍，只要三位队友的训练计划时间段有重合就可以组队，并且只要有一名队员不同则视为队伍组合不同。

因为答案数量很大，请对 $10^9+7$ 取模后输出。

输入格式

第一行有一个正整数 $n(1 \leqslant n \leqslant 10^5)$。

接下来 $n$ 行，每行有两个整数 $l_i, r_i, p_i(0 \leqslant l \leqslant 10^9, 1 \leqslant r \leqslant 10^9, l \leqslant r, 1 \leqslant q \leqslant 10^4)$ 分别代表训练计划的起始时间，结束时间，选择人数。

输出格式

输出一个整数，表示总共有多少种队伍组合，答案对 $10^9+7$ 取模。

样例

3
1 4 1
1 4 1
4 5 1

1

5
1 4 1
3 7 2
4 8 1
6 8 2
7 9 1

23