HZNUOJ

街道

Tags:
Time Limit:  1 s      Memory Limit:   32 MB
Submission:12     AC:0     Score:99.89

Description

 设有一个N*M1 N50 1M 50)的街道(如下图):

规定行人从A(1,1)出发,在街道上只能向东或北方向行走。

如下为N3M=3的街道图,从A出发到达B共有6条可供行走的路径:

  1. A-A1-A2-A5-B
  2. A-A1-A4-A5-B
  3. A-A1-A4-A7-B
  4. A-A3-A4-A5-B
  5. A-A3-A4-A7-B
  6. A-A3-A6-A7-B

若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用“*”表示的部分。

此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2,2), (8,4),此时从A出发到达B的路径仅有两条。

程序要求:

任务一:给出NM后,求出所有从A出发到达B的路径的条数。

任务二:给出NM,同时再给出此街道中的矩形障碍区域的2对顶点坐标 (X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。

Input

N M

障碍区域两对顶点坐标(若无障碍区则该行无输入)。

Output

若未给出障碍区域顶点坐标,输出任务一答案,否则输出任务二答案。

Samples

input
50 50 (2,2), (49,49)
output
2

Source

NOIP1997普及组