题目描述

COCI 的出题者必须从一堆题目中选择在下一轮中出现的题目。

题目的难度用 $1$ 到 $n$ 的整数来描述，但是对于某些题目来说，这并不容易准确地确定它们的难度。COCI 的出题者认为这些题目可以被视为有两个连续难度之一。例如，某些题目可以被视为难度为 $3$ 或 $4$。

下一轮 COCI 将包含的 $N$ 个题目。每一个难度，都会有且仅有一个题目。当然，没有题目会出现两次。

找出出题者为下一轮选择题目的不同方法的数量。我们认为两种方法是不同的仅当相同的任务分配给了不同的难度。

由于预期的结果可以非常大，输出的方案数 $\% 10^9+7$。

输入格式

输入的第一行包含整数 $N$。

第二行包含 $N$ 个整数 $A_i$，第 $i$ 个数代表困难度恰好为 $i$ 的题目的数量。

第三行输入包含 $N-1$ 个整数 $B_i$，第 $i$ 个数代表困难度为 $i$ 或 $i+1$ 的题目的数量。

输出格式

输出共一行，一个整数，表示方案数 $\% 10^9+7$。

3
3 0 1
0 1 

3

4
1 5 3 0
0 2 1 

33

提示

【样例解释#1】

共 $3$ 种方案：将难度为 $2$ 或 $3$ 的题目视为难度为 $2$ 的，因为难度为 $1$ 的题目有 $3$ 道，所以共 $3$ 种方案。

【数据范围】

对于 $100\%$ 的数据，$2\le N\le 10^5$，$0\le A_i,B_i\le 10^9$。

【说明】

本题分值按 COCI 原题设置，满分 $100$。

题目译自 COCI2010-2011 CONTEST #5 T4 HONI。