题目描述

小 Z 被指派为某一项工程的总负责人，他可以在非常多的人中（可以认为是无数多）选出 $N$ 个人执行难度系数为 $1\sim N$ 的任务。

有些人只能执行某一特定难度系数为 $i$ 任务，另一些人则可以完成相邻难度系数为 $i$ 或者 $i+1$ 的任务。

每个人只能接一个任务，每个任务只能分配给一个人。

问现在有多少种不同的分配任务的方案？

• 两种方案视为不同，如果存在某个任务在两种方案中分配的人不同。
• 因为方案数可能很大，所以输出方案数对 $1 000 000 007$ 取模的结果即可。

数据保证，一定存在一种方案可以使得每个任务 $1\sim N$ 都能分配到人来完成。

输入格式

从 honi.in 文件输入数据。

第一行包含一个正整数 $N$。

第二行包含 $N$ 个不超过 $10^9$ 的整数，第 $i$ 个整数表示只能执行难度为 $i$ 的人数。

第三行包含 $N-1$ 个不超过 $10^9$ 的整数，第 $i$ 个整数表示能执行难度为 $i$ 或 $i+1$ 的人数。

输出格式

输出到 honi.out 文件。

输出一行包含方案数 $\text{mod}$ $1 000 000 007$。

样例

3 
3 0 1 
0 1

3

4 
1 5 3 0 
0 2 1

33

样例输入3

点击链接 honi.in 下载大样例输入

样例输出3

点击链接 honi.out 下载大样例输出

说明/提示

样例 1 解释

我们可以假设有编号为 $1,2,\dots,5$ 的共 $5$ 个人，其中编号为 $1,2,3$ 共 $3$ 个人只能完成任务 $1$，编号为 $4$ 的人只能完成任务 $3$，编号为 $5$ 的人可以完成任务 $2$ 和 $3$。

1. 没有人只能完成任务 $2$，所以我们要把唯一一个个能够完成任务 $2,3$ 的人（编号为 $5$）分配去完成任务 $2$
2. 接下来，只有一个 $4$ 号可以完成任务 $3$，将他分配去任务 $3$
3. 最后，还有 $1,2,3$ 三个人可以完成任务 $1$

所以，总方案数为 $1 * 1 * 3=3$

样例 2 解释

我们假设编号为 $1$ 的人只能完成任务 $1$，编号为 $[2,6]$ 共 $5$ 个人只能完成任务 $2$，编号为 $[7,9]$ 共 $3$ 个人只能完成任务 $3$，没有人只能完成任务 $4$，有编号为 $10,11$ 的人可以完成任务 $2,3$，编号为 $12$ 的人可以完成任务 $4$。

1. 因为没有人只能完成任务 $4$，所以我们必须选择 $12$ 号完成任务 $4$
2. 只有 $1$ 号可以完成任务 $1$，所以我们必须选择 $1$ 号完成任务 $1$
3. 现在只能完成任务 $2$ 的有 $[2,6]$ 共 $5$ 人，只能完成任务 $3$ 的有 $[7,9]$ 共 $3$ 人，这里有 $3 * 5 = 15$ 种方案
4. 如果考虑 $10,11$ 可以完成任务 $2,3$ 的人，那么这里有 $2$ 种去完成任务 $2$ 或者任务 $3$，总共方案数为 $2 * 3 + 5 * 2 = 16$ 种
5. 另外，$10,11$ 两个人可以一个去任务 $2$，另一个去任务 $3$，这里又有 $2$ 种方案

所以，总方案数为 $15+16+2=33$ 种。

数据范围

$30\%$ 的数据，总人数不超过 $10$；

$50\%$ 的数据，$N \le 5$；

$60\%$ 的数据，$N \le 20$；

$70\%$ 的数据，$N \le 1000$；

$100\%$ 的数据，$N \le 10^5$，并且保证第二行以及第三行的每一个整数为不超过 $10^9 的非负整数$。