题目描述

Snuke is standing on a two-dimensional plane. In one operation, he can move by $1$ in the positive $x$-direction, or move by $1$ in the positive $y$-direction.

Let us define a function $f(r, c)$ as follows:

• $f(r,c) :=$ (The number of paths from the point $(0, 0)$ to the point $(r, c)$ that Snuke can trace by repeating the operation above)

Given are integers $r_1$, $r_2$, $c_1$, and $c_2$. Find the sum of $f(i, j)$ over all pair of integers $(i, j)$ such that $r_1 ≤ i ≤ r_2$ and $c_1 ≤ j ≤ c_2$, and compute this value mod $(10^9+7)$.

斯努克站在一个二维平面上。在一次操作中，他可以向正 $x$ 方向移动 $1$ ，也可以向正 $y$ 方向移动 $1$ 。

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

• $f(r,c) :=$ （重复上述操作，斯努克可以追踪到的从点 {221988} 到点 $(r, c)$ 的路径数）

已知整数 $r_1$ 、 $r_2$ 、 $c_1$ 和 $c_2$ 。求所有一对整数 $(i, j)$ 中 $r_1 ≤ i ≤ r_2$ 和 $c_1 ≤ j ≤ c_2$ 的和 $f(i, j)$ ，并计算这个值的模数 $(10^9+7)$ 。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $f(i, j)$ mod $(10^9+7)$ 的和。

样例 #1

样例输入 #1

1 1 2 2

样例输出 #1

14

样例 #2

样例输入 #2

314 159 2653 589

样例输出 #2

314 159 2653 589

说明

数据规模与约定

• $1 ≤ r_1 ≤ r_2 ≤ 10^6$
• $1 ≤ c_1 ≤ c_2 ≤ 10^6$
• 所有输入值均为整数。

样例 $1$ 解释

例如，从点 $(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$ 。