AT_abc154_f [ABC154F] Many Many Paths

题目描述

有一个二维平面。站在这个平面上的すぬけ君每次操作可以向 $x$ 轴正方向移动 $1$，或者向 $y$ 轴正方向移动 $1$。

定义函数 $f(r,c)$ 如下：

• $f(r,c)\ :=$（すぬけ君从点 $(0,0)$ 经过上述操作到达点 $(r,c)$ 的路径条数）

给定整数 $r_1,\ r_2,\ c_1,\ c_2$。请计算所有满足 $r_1 \leq i \leq r_2$ 且 $c_1 \leq j \leq c_2$ 的整数对 $(i,j)$ 的 $f(i,j)$ 之和，并对 $10^9+7$ 取模。

输入格式

输入以如下格式从标准输入给出。

$r_1$ $c_1$ $r_2$ $c_2$

输出格式

输出 $f(i,j)$ 的总和对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

1 1 2 2

输出 #1

14

输入输出样例 #2

输入 #2

314 159 2653 589

输出 #2

602215194

说明/提示

限制条件

• $1 \leq r_1 \leq r_2 \leq 10^6$
• $1 \leq c_1 \leq c_2 \leq 10^6$
• 所有输入均为整数

样例解释 1

例如，从点 $(0,0)$ 到点 $(1,1)$ 的路径有 $(0,0) \to (0,1) \to (1,1)$ 和 $(0,0) \to (1,0) \to (1,1)$ 共 $2$ 条，因此 $f(1,1)=2$。同理，$f(1,2)=3$，$f(2,1)=3$，$f(2,2)=6$，所以所求总和为 $14$。

由 ChatGPT 4.1 翻译