← 返回题目列表

AtCoder · abc154_f

F. 很多很多路径

中文机器翻译题面 查看原题

分数: 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