#582. 1586. 路径统计path

1586. 路径统计path

#1586. 路径统计path

题目描述

一个矩阵由r行c列共r*c个小正方形组成。行从下到上编号为1到r,列从左到右编号为1到c。所有坐标都是(row,colmn)的形式。 给出n个特殊点的坐标,保证特殊点在矩阵内,依次编号为1到n,从(1,1)到(r,c)的包含严格k个特殊点的路径称为k型路径。 同时路径必须遵循以下规则: 1. 每次你只能向上或向右。即你只能从(x,y)走到(x+1,y)或(x,y+1) 2. 特殊点在路径中出现的顺序必须与给出的顺序相同,即如果特殊点a出现在特殊点b之前,那么a必须小于b。 请输出0型路径,1型路径…,n型路径的条数mod 1000007

输入格式

第一行两个数R,C。 第二行描述1-n号特殊点的行号。请读到行尾。 第二行描述1-n号特殊点的列号。

输出格式

N+1个用空格隔开的整数,分别表示1型路径…,n型路径的条数mod 1000007

样例

样例输入

3  

3  

2 3  

2 2  

样例输出

1 3 2  

  

【样例解释】  

0型路径  

(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)  

1型路径  

(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)  

(1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)  

(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)  

2型路径  

(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)  

(1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)  

  

【数据规模】  

对于100%数据  

1<=R,C<=50  

0<=N<=50  

数据范围与提示