小$S$在打算给ZR出题。

题目的难度一共分为$N$阶，标号从$1$到$N$。

有的题目小$S$已经很确定了，难度就是$x$。有的题目小$S$并不是很确定，难度可能是$x$，也可能是$x+1$，标哪一种都可以。

现在，小$S$打算选出$N$道题，再标完不确定难度的题之后,满足任意两题难度不相同。

有多少种方案呢？（两种方案不同当且仅当选的题不同或者选出来的某一题标的难度不同）

输入格式

第一行一个整数$n$。

接下来一行，$N$个整数，其中第$i$个表示确定难度是$i$的题的个数。

接下来一行，$N-1$个整数，其中第$i$个表示难度是$i$或$i+1$的题的个数。

输出格式

输出答案对$10^9+7$取模的值。。

样例1

input

3
3 0 1
0 1   

output

3 

样例2

input

4
1 5 3 0
0 2 1 

output

33

数据范围

$100\%$的数据：$1 \le n \le 10^5$，,输入的数小于$\le 10^9$.

** 时间限制：1S **

** 空间限制：256MB **