Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Placing Jinas

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputWe 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

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

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

Examples

Input

2 2 2 0

Output

5

Input

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

Output

2596

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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2022 14:17:14 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|