CF1696E.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 \gt 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 \lt 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$.

我们称一个无穷序列 $a_{0}, a_{1}, a_2, \ldots$ 是非增的，当且仅当对所有 $i\ge 0$，均有 $a_i \ge a_{i+1}$。

存在一个向右和向下无限延伸的网格。左上角单元格坐标为 $(0,0)$。行号从上到下编号为 $0, 1, 2, \ldots$，列号从左到右编号为 $0, 1, 2, \ldots$。

另给定一个非增的无穷序列 $a_{0}, a_{1}, a_2, \ldots$。你已知 $a_0$, $a_1$, $\ldots$, $a_n$；对所有 $i > n$，定义 $a_i = 0$。对任意坐标对 $(x, y)$，位于第 $x$ 行、第 $y$ 列交点处的单元格 $(x,y)$ 为白色当且仅当 $y < a_x$，否则为黑色。

初始时，在位置 $(0,0)$ 上有一个名为 Jina 的玩偶。你可以执行如下操作：

• 选择一个位于 $(x,y)$ 的玩偶，将其移除，并在 $(x,y+1)$ 放置一个玩偶，在 $(x+1,y)$ 放置另一个玩偶。

注意：同一单元格中可同时存在多个玩偶；每次操作仅移除一个玩偶。你的目标是使所有白色单元格中均不含任何玩偶（即每个白色单元格中的玩偶数量为 $0$）。

达成该目标所需的最少操作次数是多少？请输出答案对 $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.

输入的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）。

输入的第二行包含 $n+1$ 个整数 $a_0,a_1,\ldots,a_n$（$0\le a_i\le 2\cdot 10^5$）。

保证序列 $a$ 是非递增的。

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

输出一个整数——该问题的答案对 $10^9+7$ 取模的结果。

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.

考虑第一个例子。在给定的网格中，单元格 $(0,0)$、$(0,1)$、$(1,0)$、$(1,1)$ 为白色，其余所有单元格均为黑色。我们使用三元组来描述网格：三元组 $(x,y,z)$ 表示在单元格 $(x,y)$ 上放置了 $z$ 个玩偶。初始时网格的状态为 $(0,0,1)$。

一种最优的操作序列如下：

• 对 $(0,0)$ 执行操作。此时网格状态变为 $(1,0,1),(0,1,1)$。
• 对 $(0,1)$ 执行操作。此时网格状态变为 $(1,0,1),(1,1,1),(0,2,1)$。
• 对 $(1,0)$ 执行操作。此时网格状态变为 $(1,1,2),(0,2,1),(2,0,1)$。
• 对 $(1,1)$ 执行操作。此时网格状态变为 $(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$。
• 对 $(1,1)$ 执行操作。此时网格状态变为 $(0,2,1),(2,0,1),(1,2,2),(2,1,2)$。

此时所有白色单元格中玩偶数量均为 $0$，因此我们以 $5$ 次操作达成了目标。