#1586. 路径统计path

内存限制:162 MiB 时间限制:5 Sec

题目描述

一个矩阵由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

数据范围与提示