分数: 600 点
问题陈述
Snuke 站在二维平面上。在一次操作中,他可以移动 1 积极 x-方向,或移动 1 积极 y- 方向。
让我们定义一个函数 f(r, c) 如下:
- f(r,c) := (从该点开始的路径数 (0, 0) 说到点子上 (r, c) Snuke可以通过重复上述操作来追踪)
给定的是整数 r_1, r_2, c_1,和 c_2。 求总和 f(i, j) 所有整数对 (i, j) 这样 r_1 ≤ i ≤ r_2 和 c_1 ≤ j ≤ c_2,并计算该值模 (10^9+7).
约束
- 1 ≤ r_1 ≤ r_2 ≤ 10^6
- 1 ≤ c_1 ≤ c_2 ≤ 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
r_1 c_1 r_2 c_2
输出
打印总和 f(i, j) 模数 (10^9+7).
示例输入 1
1 1 2 2
示例输出 1
14
例如,从点出发有两条路径 (0, 0) 说到点子上 (1, 1): (0,0) → (0,1) → (1,1) 和 (0,0) → (1,0) → (1,1),所以 f(1,1)=2.
同样, f(1,2)=3, f(2,1)=3,和 f(2,2)=6。因此,总和是 14.
示例输入 2
314 159 2653 589
示例输出 2
602215194