题目描述

一个矩阵由 $r$ 行 $c$ 列共 $r\times c$ 个小正方形组成。行从下到上编号为 $1\sim r$，列从左到右编号为 $1\sim c$。所有坐标都是 $(\text{row},\text{colmn})$ 的形式。 给出 $n$ 个特殊点的坐标，保证特殊点在矩阵内，依次编号为 $1\sim 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$。
• 第二行：$n$ 个数，描述 $1\sim n$ 号特殊点的行号。
• 第三行：$n$ 个数，描述 $1\sim n$ 号特殊点的列号。

输出格式

• 第一行：$n+1$ 个用空格隔开的整数，分别表示从 $0$ 型路径到 $n$ 型路径的条数，对 $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\leq r,c \leq 50$，$0\leq n \leq 50$。

说明

由于原题面样例输入格式表述有错误，在完全不影响原题意的情况下对题面进行了部分改动。