Placing Jinas
Contest: Codeforces Global Round 21
Difficulty rating: 2000
Tags: combinatorics, math

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

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Consider the first example. In the given grid, cells $$$(0,0),(0,1),(1,0),(1,1)$$$ are white, and all other cells are black. Let us use triples to describe the grid: triple $$$(x,y,z)$$$ means that there are $$$z$$$ dolls placed on cell $$$(x,y)$$$. Initially the state of the grid is $$$(0,0,1)$$$.

One of the optimal sequence of operations is as follows:

- Do the operation with $$$(0,0)$$$. Now the state of the grid is $$$(1,0,1),(0,1,1)$$$.
- Do the operation with $$$(0,1)$$$. Now the state of the grid is $$$(1,0,1),(1,1,1),(0,2,1)$$$.
- Do the operation with $$$(1,0)$$$. Now the state of the grid is $$$(1,1,2),(0,2,1),(2,0,1)$$$.
- Do the operation with $$$(1,1)$$$. Now the state of the grid is $$$(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$$$.
- Do the operation with $$$(1,1)$$$. Now the state of the grid is $$$(0,2,1),(2,0,1),(1,2,2),(2,1,2)$$$.

Now all white cells contain $$$0$$$ dolls, so we have achieved the goal with $$$5$$$ operations.

Example input:
2
2 2 0

Example output:
5

Example input:
10
12 11 8 8 6 6 6 5 3 2 1

Example output:
2596

Editorial:
Let us find out the number of operations we do on a specific cell $$$(i,j)$$$, call it $$$f(i,j)$$$.
Every operation done on $$$(i-1,j)$$$ will lead to one doll on $$$(i,j)$$$, thus consuming one operation on $$$(i,j)$$$. Similar observation holds for $$$(i,j-1)$$$.
Thus, $$$f(i,j)=f(i,j-1)+f(i-1,j)$$$ (given that $$$(i,j),(i-1,j),(i,j-1)$$$ are all white cells). Note that $$$a$$$ is non-increasing: this means that if $$$(i,j)$$$ is white, $$$(i-1,j),(i,j-1)$$$ will both be white. So we can conclude that $$$f(i,j)=f(i,j-1)+f(i-1,j)$$$ always holds as long as $$$(i,j)$$$ is white.
Another way to see the formula is $$$f(i,j)$$$ is the number of ways to go from $$$(0,0)$$$ to $$$(i,j)$$$, only going down or right by 1 step. This implies that $$$f(i,j)=\binom{i+j}j$$$.
From this, we know that the answer is $$$\sum_{i=0}^n\sum_{j=0}^{a_i-1} \binom{i+j}{i}$$$. With the equation $$$\sum_{i=0}^k\binom{n+i}n=\binom{n+k+1}{n+1}$$$, we know that the answer is $$$\sum_{i=0}^n\binom{i+a_i}{i+1}$$$.
The time complexity is $$$O(n+V)$$$, where $$$V=\max a_i$$$.