题目描述

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

input

2
1 2 3
3 2 1

output

4

$D(T_1,T_2)=4$

样例 2

input

3
1 3 2
4 0 7
2 2 9

output

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