Score : $600$ points

Problem Statement

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 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$, and compute this value modulo $(10^9+7)$.

Constraints

• $1 \leq r_1 \leq r_2 \leq 10^6$
• $1 \leq c_1 \leq c_2 \leq 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the sum of $f(i, j)$ modulo $(10^9+7)$.

1 1 2 2

14

For example, there are two paths from the point $(0, 0)$ to the point $(1, 1)$: $(0,0)$ → $(0,1)$ → $(1,1)$ and $(0,0)$ → $(1,0)$ → $(1,1)$, so $f(1,1)=2$.

Similarly, $f(1,2)=3$, $f(2,1)=3$, and $f(2,2)=6$. Thus, the sum is $14$.

314 159 2653 589

602215194