题目描述
题目大意
斯努克站在一个二维平面上。
在一次操作中,他可以向 x 轴正方向或是 y 轴正方向移动一步。
定义函数 f(r,c) 为通过上述操作,斯努克从 (0,0) 走到 (r,c) 的方案总数。
现在给定 r1,r2,c1 和 c2 ,请你求出所有 f(i,j) 之和,其中 r1≤i≤r2 且 c1≤j≤c2 。形式化的,请你求出
$\ \ \ \ \ \ \sum\limits_{i=r_1}^{r_2} \sum\limits_{j=c_1}^{c_2}f(i,j)$
的值。
由于结果可能很大,请将结果对 109+7 取模。
输入
一行输入四个整数r1,c1,r2,c2
输出
输出f(i,j)的和对 109+7 取模。
1 1 2 2
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。
314 159 2653 589
602215194
提示
- 1 < = r1 < = r2 < = 106
- 1 < = c1 < = c2 < = 106