题目描述

高橋君はバーベキューをしようとしています。 バーベキューでは $2$ 本の串にいくつかの具材を刺した串焼きを $1$ 個作る予定です。

串焼きセットが $N$ 個あり、$i$ 番目のセットには串が $1$ 本、肉が $A_i$ 個、野菜が $B_i$ 個入っています。

セットを $2$ 個選び、セット $2$ つに含まれる全ての具材を好きな順番で串 $2$ 本に刺すことを考えます。 このとき、作ることの出来る串焼きは何通り考えられるでしょうか？ ただし、串どうしは区別でき、肉どうしや野菜どうしは区別できないものとします。 答えは非常に大きな数になる可能性があるので、$10^9+7$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

作ることの出来る串焼きの種類数を $10^9+7$ で割った余りを出力せよ。

题目大意

有 $n$ 个数对 $(a_i, b_i)$，求出

$$\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} $$

答案对 $10 ^ 9 + 7$ 取模。

感谢 @psk011102 提供的翻译

3
1 1
1 1
2 1

26

提示

制約

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

Sample Explanation 1

図のような $26$ 通りの串焼きを作ることが出来ます。 灰色の棒は串を表しており、串に書かれた数はその串が含まれていたセットの番号を表しています。 また、茶色の長方形は肉、緑色の長方形は野菜を表しています。