Problem Statement

There are $N$ buildings along AtCoder road. Initially, the $i$-th building from the left has $A_i$ stories.

Takahashi, the president of ARC Wrecker, Inc., can do the following operation any number of times, possibly zero:

• Choose a positive integer $X$ that he likes and shoot a cannonball at that height, which decreases by $1$ the number of stories in each building with $X$ or more stories.

Find the number of possible final sceneries of buildings, modulo ($10^{9} + 7$).

We consider two sceneries A and B different when the following holds:

• let $P_i$ be the number of stories of the $i$-th building from the left in scenery A;
• let $Q_i$ be the number of stories of the $i$-th building from the left in scenery B;
• we consider sceneries A and B different when $P_i \neq Q_i$ for one or more indices $i$.

Constraints

• $1 \leq N \leq 100000$
• $1 \leq A_i \leq 10^{9}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.