[AGC001E] BBQ Hard

题意翻译

有 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}$$ 答案对1e9+7取模 感谢@psk011102 提供的翻译

题目描述

[problemUrl]: https://agc001.contest.atcoder.jp/tasks/agc001_e 高橋君はバーベキューをしようとしています。 バーベキューでは $ 2 $ 本の串にいくつかの具材を刺した_串焼き_を $ 1 $ 個作る予定です。 串焼きセットが $ N $ 個あり、 $ i $ 番目のセットには串が $ 1 $ 本、肉が $ A_i $ 個、野菜が $ B_i $ 個入っています。 セットを $ 2 $ 個選び、セット $ 2 $ つに含まれる全ての具材を好きな順番で串 $ 2 $ 本に刺すことを考えます。 このとき、作ることの出来る串焼きは何通り考えられるでしょうか? ただし、串どうしは区別でき、肉どうしや野菜どうしは区別できないものとします。 答えは非常に大きな数になる可能性があるので、 $ 10^9+7 $ で割った余りを求めてください。

输入输出格式

输入格式


The input is given from Standard Input in the following format: ``` $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $ ```

输出格式


Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

3
1 1
1 1
2 1

输出样例 #1

26

输入样例 #2

3
1 1
1 1
2 1

输出样例 #2

26

说明

### 制約 - $ 2≦N≦200,000 $ - $ 1≦A_i≦2000,\ 1≦B_i≦2000 $ ### Problem Statement Snuke is having another barbeque party. This time, he will make one serving of _Skewer Meal_. He has a stock of $ N $ _Skewer Meal Packs_. The $ i $ -th Skewer Meal Pack contains one skewer, $ A_i $ pieces of beef and $ B_i $ pieces of green pepper. All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable. To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper. (Remaining Skewer Meal Packs will not be used.) Then, all those pieces of food are threaded onto both skewers, one by one, in any order. (See the image in the Sample section for better understanding.) In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different. Since this number can be extremely large, find it modulo $ 10^9+7 $ . ### Constraints - $ 2≦N≦200,000 $ - $ 1≦A_i≦2000,\ 1≦B_i≦2000 $ ### Sample Explanation 1 図のような $ 26 $ 通りの串焼きを作ることが出来ます。 灰色の棒は串を表しており、串に書かれた数はその串が含まれていたセットの番号を表しています。 また、茶色の長方形は肉、緑色の長方形は野菜を表しています。 ![ebbq.png](https://cdn.luogu.com.cn/upload/vjudge_pic/AT1983/b35502647869bc967112b730d0a703175c39c511.png) ### Sample Explanation 2 The $ 26 $ ways of making a Skewer Meal are shown below. Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer. Brown and green rectangles represent pieces of beef and green pepper, respectively. ![ebbq.png](https://cdn.luogu.com.cn/upload/vjudge_pic/AT1983/b35502647869bc967112b730d0a703175c39c511.png)