F - 许多的路径

得分：600分

问题描述

Snuke站在一个二维平面上。在一次操作中，他可以向正x方向移动1个单位，或者向正y方向移动1个单位。

我们定义一个函数$f(r, c)$如下：

• $f(r,c) := $ （点$(0, 0)$到点$(r, c)$的路径数量，Snuke可以通过重复上述操作轨迹得到）

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

约束条件

• $1 ≤ r_1 ≤ r_2 ≤ 10^6$
• $1 ≤ c_1 ≤ c_2 ≤ 10^6$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

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

输出

打印对$(10^9+7)$取模之后的$f(i, j)$的和。

1 1 2 2

14

例如，从点$(0, 0)$到点$(1, 1)$有两条路径：$(0,0)$ → $(0,1)$ → $(1,1)$ 和 $(0,0)$ → $(1,0)$ → $(1,1)$，所以$f(1,1)=2$。

类似地，$f(1,2)=3$，$f(2,1)=3$，$f(2,2)=6$。因此，和为$14$。

314 159 2653 589

602215194