#ABC154F. Many Many Paths

Many Many Paths

题目描述

Snuke is standing on a two-dimensional plane. In one operation, he can move by 11 in the positive xx-direction, or move by 11 in the positive yy-direction.

Let us define a function f(r,c)f(r, c) as follows:

  • f(r,c):=f(r,c) := (The number of paths from the point (0,0)(0, 0) to the point (r,c)(r, c) that Snuke can trace by repeating the operation above)

Given are integers r1r_1, r2r_2, c1c_1, and c2c_2. Find the sum of f(i,j)f(i, j) over all pair of integers (i,j)(i, j) such that r1ir2r_1 ≤ i ≤ r_2 and c1jc2c_1 ≤ j ≤ c_2, and compute this value mod (109+7)(10^9+7).

斯努克站在一个二维平面上。在一次操作中,他可以向正 xx 方向移动 11 ,也可以向正 yy 方向移动 11

让我们定义函数 f(r,c)f(r, c) 如下:

  • f(r,c):=f(r,c) := (重复上述操作,斯努克可以追踪到的从点 {221988} 到点 (r,c)(r, c) 的路径数)

已知整数 r1r_1r2r_2c1c_1c2c_2 。求所有一对整数 (i,j)(i, j)r1ir2r_1 ≤ i ≤ r_2c1jc2c_1 ≤ j ≤ c_2 的和 f(i,j)f(i, j) ,并计算这个值的模数 (109+7)(10^9+7)

输入格式

输入内容按以下格式标准输入:

r1r_1 c1c_1 r2r_2 c2c_2

输出格式

打印 f(i,j)f(i, j) mod (109+7)(10^9+7) 的和。

样例 #1

样例输入 #1

1 1 2 2

样例输出 #1

14

样例 #2

样例输入 #2

314 159 2653 589

样例输出 #2

314 159 2653 589

说明

数据规模与约定

  • 1r1r21061 ≤ r_1 ≤ r_2 ≤ 10^6
  • 1c1c21061 ≤ c_1 ≤ c_2 ≤ 10^6
  • 所有输入值均为整数。

样例 11 解释

例如,从点 (0,0)(0, 0) 到点 (1,1)(1, 1) 有两条路径: (0,0)(0,0)(0,1)(0,1)(1,1)(1,1)(0,0)(0,0) 。→ (1,0)(1,0)(1,1)(1,1) ,所以是 f(1,1)=2f(1,1)=2

类似地, f(1,2)=3f(1,2)=3f(2,1)=3f(2,1)=3f(2,2)=6f(2,2)=6 。因此,总和为 1414