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{.}$

Source: hackerrank | Difficulty: HARD
Tags: Matrices


Solutions:
def insertion_sort(a):
	for i in range(0, len(a) - 1):
		j = i
		while a[j] > a[j + 1] and j >= 0:
			temp = a[j]
			a[j] = a[j + 1]
			a[j + 1] = temp
			j -= 1
	return a

def merge_lists(a, b):
	final_list = []
	pos_a = 0
	pos_b = 0
	while pos_a + pos_b < len(a) + len(b):
		if pos_a < len(a) and pos_b < len(b) and (a[pos_a] <= b[pos_b]):
			final_list.append(a[pos_a])
			pos_a += 1
		elif pos_a < len(a) and pos_b < len(b) and (a[pos_a] > b[pos_b]):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a == len(a) and pos_b < len(b):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a < len(a) and pos_b == len(b):
			final_list.append(a[pos_a])
			pos_a += 1
		else:
			print('error')
	return final_list

def merge_sort(a):
	if len(a) < 10:
		return insertion_sort(a)
	else:
		return merge_lists(merge_sort(a[0:len(a) // 2]), merge_sort(a[len(a) // 2:len(a)]))

def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def evaluateP(b, a, mod):
	eval = 0
	x = 1
	for i in range(0, len(b)):
		eval += b[i] * x % mod
		x *= a
		x %= mod
	return eval % mod

def evaluateQ(a, a_i, mod):
	eval = 1
	for i in range(0, len(a)):
		if a_i - a[i] != 0:
			eval *= a_i - a[i]
			eval %= mod
	return eval % mod

def rationalSums(n, a, b):
	mod = pow(10, 9) + 7
	neg_one = pow_mod(mod - 1, mod - 2, mod)
	C = [0 for x in range(0, len(a))]
	for i in range(0, len(a)):
		if (len(a) + 1) % 2:
			C[i] = neg_one * evaluateP(b, mod - a[i], mod) * pow_mod(evaluateQ(a, a[i], mod), mod - 2, mod) % mod
		else:
			C[i] = evaluateP(b, mod - a[i], mod) * pow_mod(evaluateQ(a, a[i], mod), mod - 2, mod) % mod
	inverses = [1 for _ in range(0, 5001)]
	sum_of_inverses = [0 for _ in range(-1, 5001)]
	for i in range(1, 5001):
		inverses[i] = pow_mod(i, mod - 2, mod)
		if i > 1:
			sum_of_inverses[i] = (sum_of_inverses[i - 1] + inverses[i]) % mod
		else:
			sum_of_inverses[1] = 1
	s = 0
	for j in range(0, len(a)):
		s += C[j] * (sum_of_inverses[a[len(a) - 1]] - sum_of_inverses[a[j]])
		s %= mod
	return s
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))
result = rationalSums(n, merge_sort(a), b)
print(result)