题目描述

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

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

• $f(r,c) :=$（小 Snuke 可以通过重复上述操作从点 $(0, 0)$ 到达点 $(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)$ 求模。

约束条件

• $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 1 2 2

示例输出 1

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$。

示例输入 2

314 159 2653 589

示例输出 2

602215194