Many Many Paths

题目描述

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 ≤ i ≤ r_2$ 且 $c_1 ≤ j ≤ c_2$ 的整数对 $(i, j)$ 上 $f(i, j)$ 的和，并将该值对 $(10^9+7)$ 取模。

输入格式

输入从标准输入给出，格式如下： $r_1$ $c_1$ $r_2$ $c_2$

输出格式

输出对 $(10^9+7)$ 取模后的 $f(i, j)$ 之和。

1 1 2 2

14

314 159 2653 589

602215194

提示

$1 ≤ r_1 ≤ r_2 ≤ 10^6$ $1 ≤ c_1 ≤ c_2 ≤ 10^6$ 输入中的所有值均为整数。例如，从点 $(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$。

标签: AtCoder|abc154F

来源

AtCoder|abc154F