上学路上
测试数据来自 system/1943
描述
小雪与小可可吵架了,他们决定以后互相再也不理对方了。尤其是,他们希望以后上学的路上不会再相遇。
我们将他们所在城市的道路网视作无限大的正交网格图,每一个整数点 (x,y) 对应了一个路口,相邻两个整数点之间有一条平行于 x 轴或平行于 y 轴的道路,其道路长度为 1。已经知道小雪家住在 (x_1,0) 处的路口附近,小可可的家住在 (x_2,0) 处的路口附近。另外我们还知道,小雪的学校在 (0,y_1) 处的路口附近,小可可的学校在 (0,y_2) 处的路口附近。其中保证 x_1 < x_2 且 y_1 < y_2。
因为上学不能迟到,所以小雪和小可可总是希望可以走最短路径去上学。同时为了避免见面,希望他们所选择的路线可以没有交点。
格式
输入格式
输入的第一行输入四个正整数,依次为 x_1, x_2, y_1, y_2,满足 x_1 < x_2 且 y_1 < y_2。
输出格式
在输出中,输出一个非负整数,表示可行方案的总数 ans 关于常数 10^9+7 取余后的值。
样例1
样例输入1
1 2 1 2
样例输出1
3
样例2
样例输入2
2 3 2 4
样例输出2
60
样例3
样例输入3
4 9 3 13
样例输出3
16886100
限制
对于30%的数据,0 < x_1,x_2,y_1,y_2<=500。
对于70%的数据,0 < x_1,x_2,y_1,y_2<=3000。
对于100%的数据,0 < x_1,x_2,y_1,y_2<=100000。
提示
对于样例一来说,一共有三种可行方案,如下图所示。
图丢了>_<
来源
AHOI 2015
信息
- ID
- 1875
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者