3. на меня

【题目背景】

「И наменятоже обрати внимание.」

「啊？你说什么？」

「没有啊？我只是说『这家伙真的很蠢』。」

「可以别用俄语骂我吗？」

                              ——《不时轻声地以俄语遮羞的邻座艾莉同学》

大洋里

【题目描述】

给定一个整数 $n$ 和两个数组$a$,$b$,求:

$$\sum\limits_{i=1}^n{\sum\limits_{j=i+1}^nC_{a_i+a_j+b_i+b_j}^{a_i+a_j}} \% p$$

【输入格式】

第一行两个整数 $n , p$

接下来$2$ ~ $n+1$行,每行两个数 $a_i$,$b_i$

【输出格式】

输出一行一个整数，对表示所求答案。

【样例输入】

3 1000000007
1 1
1 1
2 1

【样例输出】

26

【样例说明】

对于第一组样例,结果为:

$C_4^2+C_5^3+C_5^3=26$

【数据规模与约定】

对于 $30 \%$ 的数据，$2 \le n \le 5000$

对于另外 $20 \%$ 的数据，$a_i \le 10$

对于另外 $10 \%$ 的数据，$p = 2$

对于另外 $10 \%$ 的数据，$p = 3$

对于 $100 \%$ 的数据，$2 \le n \le 2 \times 10 ^ 5, 1 \le a_i, b_i \le 2000 , 2\le p \le 2 ^ {30} - 1 $且$p$为质数

【来源】

AT_agc001_e