很多路

（manymanypaths.cpp 2s/1024MB）

题目描述

斯努克站在一个二维平面上。

在一次操作中，他可以向 $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$ 取模。

输入格式

一行，四个整数，$r_1,c_1,r_2,c_2$

输出格式

输出答案对$10^9+7$取模的结果。

样例

输入样例

1 1 2 2

输出样例

14

样例解释

数据范围与提示

$1≤r_1≤r_2≤10^6$

$1≤c_1≤c_2≤10^6$