A. Supermarket
time limit per test
2 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You are at a $$$1$$$ dollar supermarket where there are $$$n$$$ sub-shops, each second a new customer comes in every shop, $$$\bf {\text{inititally all of them are empty}}$$$.

Since this is a $$$1$$$ dollar supermarket there is only one worker. Each second this worker chooses uniformaly randomly a shop and serves all it's customers instantly.

To do some savings the boss doesn't hire extra workers unless $$$\bf{\text{all}}$$$ the shops are all floaded. That is if we denote the number of customers of the $$$i-$$$th shop to be $$$a_i$$$.

Then the shops are floaded whenever forall $$$i \in [1, n], a_i \ge b_i$$$ for some pre-fixed $$$b_i$$$.

- $$$\bf{\text{Extra constraints : }}$$$ we assume that $$$b_1 = 0$$$.

One may prove that the shops will be floaded almost certaintly, your task is to calculate the expected time at which the boss will have to hire extra workers.

It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where P and Q are coprime integers and $$$Q \not \equiv 0$$$ mod $$$10^9 + 7$$$. Print the value of $$$P\cdot Q^{-1}$$$ mod $$$10^9+7$$$.

Input

The first line of the input you will be given $$$1 \le n \le 2 \cdot 10^5$$$ the number of shops.

The second line of the input contains $$$n$$$ space separated integers $$$b_1, ... b_n (0 \le b_i \le 10^{18})$$$ and $$$b_1 = 0$$$.

Output

Output a single integer the expected time at which the boss will have to hire extra workers modulo $$$10^9 + 7$$$.

Examples
Input
3
0 1 1
Output
3
Input
8
0 7 5 6 7 10 6 7
Output
149135259