题目描述

高桥君打算进行一次烧烤。在烧烤中，他计划用两根签子串上若干食材，制作一个“串烧”。

现在有 $N$ 套串烧套装，第 $i$ 套中包含 $1$ 根签子、$A_i$ 块肉和 $B_i$ 块蔬菜。

你可以任选两套套装，将这两套中的所有食材以任意顺序同时串在两根签子上。请问，可以制作出多少种不同的串烧？注意，签子之间是有区别的，但肉和蔬菜之间没有区别。答案可能非常大，请输出对 $10^9+7$ 取模后的结果。

若你不理解题意，请看样例解释的图。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ ... $A_N$ $B_N$

输出格式

输出可以制作的不同串烧的种类数，对 $10^9+7$ 取模后的结果。

样例 1

输入

3
1 1
1 1
2 1

输出

26

说明/提示

限制条件

• $2 \leq N \leq 200,\!000$
• $1 \leq A_i \leq 2000,\ 1 \leq B_i \leq 2000$

样例解释 1

如图所示，共有 $26$ 种不同的串烧可以制作。灰色的棒代表签子，签子上的数字表示该签子来自哪一套套装。棕色的长方形代表肉，绿色的长方形代表蔬菜。

由 ChatGPT 4.1 翻译