该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

WWT刚学会了归并排序。他在书上了解到，归并排序是一个稳定的排序算法，也就是说，假如在原序列中，a_i=a_j 且i<j，令p_i表示排序后i的位置，那么满足p_i<p_j。 WWT自作主张地给每个位置i设定了权值s_i。对于一个长度为n的序列A，WWT先用归并排序给A排序，并得到p_i。令f(A)=∑_(i=1)^n▒〖s_i 〖×p〗_i 〗，WWT称f(A)为A的魅力值。 WWT已经学会了怎么在给定A的情况下，求出f(A)。他在思考一个更为深奥的哲学问题。假如A的每个元素A_i是随机的，那么E[f(A)]会是多少呢？ 具体而言，A_i的取值是[l_i,r_i]这个闭区间中的随机整数，即A_i会等概率地等于区间中的任一整数。WWT想求出在这个条件下， f(A)的期望会是多少？ 这个问题对于一个刚学会排序的小盆友而言实在是太难了，所以他找到了你，希望得到你的帮助。为了方便输出，不妨设f(A)=x/y，其中gcd⁡(x,y)=1。请输出x×y^(-1) mod (〖10〗^9+7)的值。其中y^(-1)表示y在模〖10〗^9+7意义下的逆元。(详见PDF)

Input Format

输入文件名为sort.in。 第一行包含一个整数n。 接下来n行，每行三个整数s_i,l_i,r_i，表示A_i的值为[l_i,r_i]中的随机整数。

Output Format

输出文件名为sort.out。 输出一个整数，表示答案。

Sample

【输入样例1】

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

【输出样例1】

650000033

【输入样例1】

10
53736 68 512
82493 870 920
77300 206 576
63900 4 565
68675 0 488
13610 4 922
57472 614 825
37474 394 970
51896 398 766
77136 656 723

【输出样例1】

743178372

Hint

对于20%的数据，n≤6,0≤l_i≤r_i≤15 对于40%的数据，n≤10,0≤l_i≤r_i≤20 对于60%的数据，0≤l_i≤r_i≤1000 对于100%的数据，n≤〖10〗^5,0≤l_i≤r_i≤〖10〗^9,0≤s_i≤〖10〗^9