Placing Jinas

题意翻译

你有一张残缺的有 $n+1$ 行的网格纸，第 $i$ 行只有前 $A_i$ 格 $(A_i\geq A_{i+1})$ 。在一开始，在第一行的第一格写着一个数 $1$ ，其他格子上写的都是 $0$ 。 接下来，你可以进行若干次操作，每次操作可以将格子上任意位置 $(i,j)$ ，将上面的数减一，并将 $(i+1,j)$ 和 $(i,j+1)$ 上的数加一。特别的，如果即使在纸的边界上，你也可以进行这一操作，这会使得在格子外的加法无效。 现在，你需要求出使网格纸上的数全部变成 $0$ 的最少操作次数对 $10^9+7$ 取模的结果 $A_i,n\leq 2\times 10^5$

题目描述

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

输入输出样例

输入样例 #1

2
2 2 0

输出样例 #1

5

输入样例 #2

10
12 11 8 8 6 6 6 5 3 2 1

输出样例 #2

2596

说明

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.

题目大意：
你有一个残缺的网格纸，有n+1行，第i行只有前A_i格(A_i≥A_{i+1})。一开始，在第一行的第一格写着一个数1，其他格子上写的都是0。你可以进行若干次操作，每次操作可以将格子上任意位置(i,j)，将上面的数减一，并将(i+1,j)和(i,j+1)上的数加一。特别的，如果即使在纸的边界上，你也可以进行这一操作，这会使得在格子外的加法无效。你需要求出使网格纸上的数全部变成0的最少操作次数对10^9+7取模的结果。

输入输出数据格式：
输入格式：
第一行包含一个整数n (1≤n≤2×10^5)。
第二行包含n+1个整数a_0,a_1,…,a_n (0≤a_i≤2×10^5)。
保证序列a是非递增的。

输出格式：
打印一个整数——问题的答案，模10^9+7。题目大意： 你有一个残缺的网格纸，有n+1行，第i行只有前A_i格(A_i≥A_{i+1})。一开始，在第一行的第一格写着一个数1，其他格子上写的都是0。你可以进行若干次操作，每次操作可以将格子上任意位置(i,j)，将上面的数减一，并将(i+1,j)和(i,j+1)上的数加一。特别的，如果即使在纸的边界上，你也可以进行这一操作，这会使得在格子外的加法无效。你需要求出使网格纸上的数全部变成0的最少操作次数对10^9+7取模的结果。 输入输出数据格式： 输入格式： 第一行包含一个整数n (1≤n≤2×10^5)。 第二行包含n+1个整数a_0,a_1,…,a_n (0≤a_i≤2×10^5)。 保证序列a是非递增的。 输出格式： 打印一个整数——问题的答案，模10^9+7。