题目描述

对于每对三元组 $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

4

$D(T_1,T_2) = 4$

样例2：

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