路径统计path

一个矩阵由 $r$ 行 $c$ 列共 $r\times c$ 个小正方形组成。行从下到上编号为 $1$ 到 $r$，列从左到右编号为 $1$ 到 $c$。所有坐标均表示为 $(\text{行号},\text{列号})$。

给出 $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$ 型路径的数量，并将结果对 $1000007$ 取模。

输入格式

输入包含若干个以空白字符分隔的整数。

前两个整数为 $R,C$。

其余共有 $2N$ 个整数，其中前 $N$ 个整数依次表示第 $1$ 到第 $N$ 个特殊点的行号，后 $N$ 个整数依次表示对应特殊点的列号。$N$ 由剩余整数总数的一半确定。

输出格式

输出 $N+1$ 个用空格隔开的整数。

第 $k+1$ 个整数表示 $k$ 型路径的数量对 $1000007$ 取模后的结果，其中 $0\le k\le N$。

样例输入

3
3
2 3
2 2

样例输出

1 3 2

数据范围

• $1\le R,C\le 50$；
• $0\le N\le 50$；
• 所有特殊点的坐标均位于矩阵内。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3
3
2 3
2 2

输出

1 3 2