From a pile of suggested tasks, authors of COCI must choose ones that will appear in the next round. 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 first line of input contains the integer \(N\) (\(2 \le N \le 100\,000\)).

The second line of input contains \(N\) integers not greater than \(10^9\). The \(i\)-th number in this line is equal to the number of tasks in the pile having difficulty exactly \(i\).

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

The first and only line of output must contain the required number of ways modulo \(1\,000\,000\,007\).

riseoj 작성

출처 COCI 2010/2011 Contest 5