We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Algebra
  4. Rational Sums

Rational Sums

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

converge, while
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 , , etc. Konstantin noted this and decided to study only special case of rational functions sums, that is

where and are polynomials and for positive integer . It can be proven that if the series converges. But, as example shows, sum of rational functions can be irrational.

After some time, Konstantin decided to consider some very special case of rational functions when

and
with constraint that 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, . The next line contains integers , separated by space. The next line contains integers .

Constraints

  • .
  • are distinct.

Subtasks

Solutions that works correctly for will score at least of points.

Output Format

If answer is irreducible fraction , print , where is multiplicative inverse of modulo . It is guaranteed that .

Sample Input 0

2
0 1
1

Sample Output 0

1

Explanation 0

the sum is

Sample Input 1

3
0 1 2
1 3

Sample Output 1

750000007

Explanation 1

the sum is