문제들 중에서, COCI의 출제자들은 각 라운드에 나타나야 할 문제들을 하나씩 반드시 골라야한다.

문제의 난이도는 1부터 N범위의 정수로 나타낸다. 하지만 몇몇 문제들은 그들의 난이도를 정확히 결정하는 것이 쉽지 않다. COCI의 출제자들은 몇몇 문제들은 현재 난이도이거나, 한단계 높은 난이도로도 고려될 수 있다고 판단했다. 예를 들어 어떤 문제는 3 또는 4의 난이도로 간주할 수 있다.

COCI의 다음 라운드는 정확히 N개의 문제들이 출제될 것이다.각각의 난이도에 대해 출제되는 문제는 정확히 하나일 것이다. (같은 난이도에 두 문제가 나오는 경우는 없다.)

출제자들이 다음 라운드를 위한 문제를 고를 수 있는 다른 경우의 수를 찾아라. 우리는 어떤 난이도에 대해 다른 문제가 그 난이도에 할당하는 경우 두 가지 방법이 다르다고 말한다.

기대되는 결과값이 매우 클 수 있으므로, 경우의 수를 10억 7로 나눈 나머지를 출력한다.

입력

• 첫 줄엔 정수 N (2 ≤ N ≤ 100 000)을 포함한다.
• 두번째 줄에는 10^9보다 크지 않은 N개의 정수들을 포함한다. i번째 숫자는 난이도 i를 가진 문제의 갯수이다.
• 세번째 줄에는 10^9보다 크지 않는 N-1개의 정수들을 포함한다.
• i번째 정수는 i또는 i+1의 난이도를 가지는 문제의 갯수이다.

출력

Difficulty of a task is described with an integer in range 1 to N. For some tasks, however, it’s not easy to exactly determine their difficulty. Authors of COCI decided that these tasks can be considered as having either one of two consecutive difficulties. For example, some task can be considered as having difficulty of either 3 or 4.

The next round of COCI will contain exactly N tasks. For each difficulty, there will be exactly one task with that difficulty. Of course, no task will appear twice.

Find the number of different ways authors can choose tasks for the next round. We say that two ways are different if for some difficulty, a different task is assigned to that difficulty.

Since the expected result can be very large, output the number of ways modulo 1 000 000 007.

입력

The third line of input contains N-1 integers not greater than 10^9. i-th number in this line is equal to the number of tasks in a pile having difficulty either i or i+1.

출력

입출력 예

입력

3
3 0 1
0 1

출력

3

입력

4
1 5 3 0
0 2 1

출력

33

출처:coci 2011
번역:Fate