## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Placing Jinas Codeforces Solution | Codeforces Problem Solution 2022

E. Placing Jinas
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

We say an infinite sequence ${a}_{0},{a}_{1},{a}_{2},\dots$ 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 $\left(0,0\right)$. 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},\dots$. You are given ${a}_{0}$${a}_{1}$$\dots$${a}_{n}$; for all $i>n$${a}_{i}=0$. For every pair of $x$$y$, the cell with coordinates $\left(x,y\right)$ (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 $\left(0,0\right)$. You can do the following operation.

• Select one doll on $\left(x,y\right)$. Remove it and place a doll on $\left(x,y+1\right)$ and place a doll on $\left(x+1,y\right)$.

Solution Click Below:-  👉
👇👇👇👇👇

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},\dots ,{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$.