题目描述

对于每对三元组 $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$ 取模）。

2
1 2 3
3 2 1

4

$D(T_1,T_2)=4$

3
1 3 2
4 0 7
2 2 9

20

$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$。