许多许多路径

题目描述

有一个 $2$ 维平面。站在平面上的 Snuke 每次操作可以沿 $x$ 轴正方向移动 $1$,或沿 $y$ 轴正方向移动 $1$。

另外,定义函数 $f(r,c)$ 如下:

• $f(r,c) :=$ (Snuke 从点 $(0,0)$ 通过重复上述操作到达点 $(r,c)$ 的路径条数)

给定整数 $r_1, r_2, c_1, c_2$。 求对所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的整数对 $(i,j)$,$f(i,j)$ 的总和,并计算除以 $(10^9+7)$ 的余数。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出 $f(i,j)$ 的总和除以 $(10^9+7)$ 的余数。

样例

1 1 2 2

14

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

314 159 2653 589

602215194

数据范围

• $1 \le r_1 \le r_2 \le 10^6$
• $1 \le c_1 \le c_2 \le 10^6$
• 输入均为整数