题目描述
对于每对三元组 Ta=(La,Ja,Ka),Tb=(Lb,Jb,Kb),
定义 Ta,Tb 之间的差值 D 为 D(Ta,Tb)=max(La−Lb,Ja−Jb,Ka−Kb)−min(La−Lb,Ja−Jb,Ka−Kb)。
现给出 n 个三元组,计算这 n 个三元组两两之间的差值的总和(对 109+7 取模)
输入格式
第一行一个整数 n。
之后的 n 行,每行三个整数,表示Li、Ji、Ki。
输出格式
输出一行,为 n 个三元组之间两两差值之和(对 109+7 取模)。
样例 1
2
1 2 3
3 2 1
4
D(T1,T2)=4
3
1 3 2
4 0 7
2 2 9
20
D(T1,T2)+D(T1,T3)+D(T2,T3)=8+8+4=20
数据范围与提示
对于 10% 的数据,n≤103;
对于 50% 的数据,n≤2×104;
对于 80% 的数据,n≤2×105,1≤Li,Ji,Ki≤107;
对于 100% 的数据,1≤n≤5×105,1≤Li,Ji,Ki≤108。