#P1317. [NOIP1997 普及组]街道路径2

[NOIP1997 普及组]街道路径2

image
若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,
如图中用“*”表示的部分。
此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2,2),(8,4),此时从 A出发到达B的路径仅有两条。
程序要求:
给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。
【输入样例】
30 40
5 5
15 15
【输出样例】
118200946737728400
【输入样例解释】
第一行表示M、N
第二行表示坐标(X1 Y1)
第二行表示坐标(X2 Y2)