题目描述

$2$ 次元平面があります。この平面上に立っているすぬけ君は、一回の操作で $x$ 軸正の方向に $1$ もしくは $y$ 軸正の方向に $1$ 移動することができます。

また、以下のように関数 $f(r,c)$ を定義します。

• $f(r,c)\ :=$ (すぬけ君が点 $(0,0)$ から点 $(r,c)$ まで上記の操作を繰り返して到達する経路の個数)

整数 $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)$ で割った余りを計算してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$f(i,j)$ の総和を $(10^9+7)$ で割った余りを出力せよ。

题目大意

斯努克站在一个二维平面上。
在一次操作中，他可以向 $x$ 轴正方向或是 $y$ 轴正方向移动一步。
定义函数 $f(r,c)$ 为通过上述操作，斯努克从 $(0,0)$ 走到 $(r,c)$ 的方案总数。
现在给定 $r_1,r_2,c_1$ 和 $c_2$ ，请你求出所有 $f(i,j)$ 之和，其中 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 。形式化的，请你求出
$\ \ \ \ \ \ \sum\limits_{i=r_1}^{r_2} \sum\limits_{j=c_1}^{c_2}f(i,j)$
的值。
由于结果可能很大，请将结果对 $10^9+7$ 取模。

1 1 2 2

14

314 159 2653 589

602215194

提示

制約

• $1\ <\ =\ r_1\ <\ =\ r_2\ <\ =\ 10^6$
• $1\ <\ =\ c_1\ <\ =\ c_2\ <\ =\ 10^6$
• 入力はすべて整数

Sample Explanation 1

例えば、点 $(0,0)$ から点 $(1,1)$ までの経路は、$(0,0)$ → $(0,1)$ → $(1,1)$ と $(0,0)$ → $(1,0)$ → $(1,1)$ の $2$ 通りあるので、 $f(1,1)=2$ です。 同様に、$f(1,2)=3$, $f(2,1)=3$, $f(2,2)=6$ なので、求める総和は $14$ です。