#1796 문제 출제

16  1 s   128 MB  

Description

제 1회 전대프연대회 담당자 백준은 모아둔 여러개의 문제들에서 이번 대회에 낼 문제를 골라야한다.

각 문제의 난이도는 1부터 N으로써 표현되어있다. 그러나 하나의 난이도로 결정짓기에 난해한 문제는 때에 따라서 두가지의 난이도로 쓰일 수 있다.

예를 들어 어떤 문제는 경우에 따라 난이도 3과 4 둘 중 하나로 표현 될 수 있다.

전대프연대회의 다음 시험에는 N개의 서로다른 난이도의 문제가 출제 되어야 한다. 물론, 하나의 문제가 두번 나올 수 없다.

대회에 출제될 문제들의 경우의 수를 찾아라. 결과가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력하라.

Input

첫번째 줄은 N(2<=N<=100000)이 입력된다.

두번째 줄은 109을 넘지 않는 정수가 N개 입력되며, 이는 문제에 책정된 난이도가 정확히 하나인 문제들을 뜻한다. 이 줄의 i번째 숫자는 난이도가 i인 문제의 수이다.

세번째 줄은 109을 넘지 않는 정수가 N-1개 입력되며, 이는 문제에 책정된 난이도가 정확히 두개인 문제들을 뜻한다. 이 줄의 i번째 숫자는 난이도가 i또는 i+1가 될 수있는 문제의 수를 뜻한다. 다시 말해서 문제가 두가지의 난이도를 가지게 될 경우에는 반드시 배정된 두개의 난이도의 차이는 1이어야 한다는 것이다.

 

Output

출제 가능한 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

Sample Input

Sample Output

3
3 0 1
0 1
3

Sample Input 2

4
1 5 3 0
0 2 1

Sample Output 2

33