#6086. Mr.Mo 的三元组

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Idvzchuscvol

题目描述

对于每对三元组 T_a=(L_a,J_a,K_a) T_b=(L_b,J_b,K_b)

定义 T_a,T_b 之间的差值 D D(T_a,T_b) = \max(L_a-L_b,J_a-J_b,K_a-K_b)-\min(L_a-L_b,J_a-J_b,K_a-K_b)

现给出 n 个三元组,计算这 n 个三元组两两之间的差值的总和(对 10^9+7 取模)

输入格式

第一行一个整数 n

之后的 n 行,每行三个整数,表示 L_i J_i K_i

输出格式

输出一行,为 n 个三元组之间两两差值之和(对 10^9+7 取模)。

样例

样例输入 1

2 
1 2 3 
3 2 1

样例输出 1

4

样例解释 1

D(T_1,T_2)=4

样例输入 2

3
1 3 2
4 0 7
2 2 9

样例输出 2

20

样例解释 2

D(T_1,T_2)+D(T_1,T_3)+D(T_2,T_3)=8+8+4=20

数据范围与提示

对于 10\% 的数据, n \leq 10^3
对于 50\% 的数据, n \leq 2\times 10^4
对于 80\% 的数据, n \leq 2\times10^5, 1 \leq L_i,J_i,K_i \leq 10 ^ 7
对于 100\% 的数据, 1 \leq n \leq 5\times10^5, 1 \leq L_i,J_i,K_i\leq 10 ^ 8