从候选题库中，COCI 的命题人必须选择一些题目用于下一轮比赛。

题目的难度用 $1$ 到 $N$ 之间的整数表示。然而，对于某些题目，很难精确确定它们的难度。COCI 的命题人决定，这些题目可以被认为具有两个连续难度之一。例如，某道题目可以被认为难度是 $3$ 或 $4$。

下一轮 COCI 将恰好包含 $N$ 道题。对于每个难度，将恰好有一道该难度的题目。当然，同一道题不能被选择两次。

求命题人选择下一轮题目的不同方案数。如果对于某个难度，分配了不同的题目，则认为两种方案是不同的。

由于结果可能非常大，请输出方案数模 $1\,000\,000\,007$ 的结果。

输入格式

第一行包含整数 $N$ ($2 \le N \le 100\,000$)。

第二行包含 $N$ 个不大于 $10^9$ 的整数。这一行中的第 $i$ 个数等于题库中难度恰好为 $i$ 的题目数量。

第三行包含 $N-1$ 个不大于 $10^9$ 的整数。这一行中的第 $i$ 个数等于题库中难度为 $i$ 或 $i+1$ 的题目数量。

输出格式

输出唯一的一行，包含所需的方案数模 $1\,000\,000\,007$ 的结果。

样例

输入样例 1

3
3 0 1
0 1

输出样例 1

3

输入样例 2

4
1 5 3 0
0 2 1

输出样例 2

33