A15261 | Placing Jinas

We say an infinite sequence $a_{0}, a_{1}, a_2, \ldots$ is non-increasing if and only if for all $i\ge 0$ , $a_i \ge a_{i+1}$ .

There is an infinite right and down grid. The upper-left cell has coordinates $(0,0)$ . Rows are numbered $0$ to infinity from top to bottom, columns are numbered from $0$ to infinity from left to right.

There is also a non-increasing infinite sequence $a_{0}, a_{1}, a_2, \ldots$ . You are given $a_0$ , $a_1$ , $\ldots$ , $a_n$ ; for all $i>n$ , $a_i=0$ . For every pair of $x$ , $y$ , the cell with coordinates $(x,y)$ (which is located at the intersection of $x$ -th row and $y$ -th column) is white if $y<a_x$ and black otherwise.

Initially there is one doll named Jina on $(0,0)$ . You can do the following operation.

- Select one doll on $(x,y)$ . Remove it and place a doll on $(x,y+1)$ and place a doll on $(x+1,y)$ .

Note that multiple dolls can be present at a cell at the same time; in one operation, you remove only one. Your goal is to make all white cells contain $0$ dolls.

What's the minimum number of operations needed to achieve the goal? Print the answer modulo $10^9+7$ .

The first line of input contains one integer $n$ ( $1\le n\le 2\cdot 10^5$ ).

The second line of input contains $n+1$ integers $a_0,a_1,\ldots,a_n$ ( $0\le a_i\le 2\cdot 10^5$ ).

It is guaranteed that the sequence $a$ is non-increasing.

Print one integer — the answer to the problem, modulo $10^9+7$ .