Today Konstantin learned about convergence of series. For instance, series

$\sum_{n=1}^{\infty}\dfrac{1}{n(n+1)}=\dfrac{1}{2}+\dfrac{1}{6}+\dfrac{1}{12}+\cdots=1\text{,}$
$\sum_{n=1}^{\infty}\dfrac{1}{n^2}=1+\dfrac{1}{4}+\dfrac{1}{9}+\dfrac{1}{16}+\cdots=\dfrac{\pi^2}{6}\text{,}$ converge, while
$\sum_{n=1}^{\infty}\dfrac{1}{n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+\cdots=+\infty$ diverges. See more at https://en.wikipedia.org/wiki/Convergent_series .

As you may note, some simple looking series can converge to quite complicated numbers, like $\frac{\pi^{2}}{6}$, $\boldsymbol{\mathrm{~e~}}$, etc. Konstantin noted this and decided to study only special case of rational functions sums, that is

$\sum_{n=1}^{\infty}\frac{P(n)}{Q(n)},$ where $\mbox{P}$ and $\mbox{Q}$ are polynomials and $Q(n)\neq0$ for positive integer $n$. It can be proven that if $\text{deg}\:P\leq\text{deg}\:Q-2$ the series converges. But, as example $\sum\limits_{n=1}^{\infty}\frac{1}{n^2}$ shows, sum of rational functions can be irrational.

After some time, Konstantin decided to consider some very special case of rational functions when $Q(x)=(x+a_1)(x+a_2).....(x+a_m)$ and $P(x)=b_0+b_1x+\cdots+b_{n-2}x^{m-2},$ with constraint that $a_1,a_2,\ldots,a_m$ are distinct non-negative integers. Fortunately, it can be proven that in this case sum of the series above is rational number. Now Konstantin want you to calculate it.

Input Format

The first line of input contains single integer, $m$. The next line contains $m$ integers $a_1,a_2,\ldots,a_m$, separated by space. The next line contains $m-1$ integers $b_0,b_1,\ldots,b_{m-2}$.

Constraints

$2\leq m\leq5000,$
$0\leq a_i\leq5000,$
$0\leq b_i\leq10^9$.
$a_1,\ldots,a_m$ are distinct.

Subtasks

Solutions that works correctly for $m\leq100$ will score at least $50\%$ of points.

Output Format

If answer is irreducible fraction $\frac{a}{b}$, print $ab^{-1}\:\text{mod}\:(10^9+7)$, where $b^{-1}$ is multiplicative inverse of $\boldsymbol{b}$ modulo $10^9+7$. It is guaranteed that $b\mod10^9+7\neq0$.

Sample Input 0
2
0 1
1

Sample Output 0
1

Explanation 0

the sum is $\sum_{n=1}^{+\infty}\dfrac{1}{n(n+1)}=\dfrac{1}{2}+\dfrac{1}{6}+\dfrac{1}{12}+\dfrac{1}{20}+\cdots=1.$

Sample Input 1
3
0 1 2
1 3

Sample Output 1
750000007

Explanation 1

the sum is $\sum_{n=1}^{+\infty}\dfrac{1+3n}{n(n+1)(n+2)}=\dfrac{4}{6}+\dfrac{7}{24}+\dfrac{10}{60}+\dfrac{13}{120}+\cdots=\dfrac{7}{4}\text{.}$

见题面

见题面