Mindol Tour

Mindol is the best rapper in the world. With the money he earned on a tour of 100 countries, he built an amusement park called Mindol Park a while ago.

The main ride in Mindol Park is a row of trampolines. There are $N+1$ trampolines numbered $0$ to $N$, placed in that order, and you play by jumping between them. Trampoline $0$ is the starting point, so from it you can jump to every other trampoline in one jump. From trampoline $i$ with $1 \le i \le N$ you can jump in one jump only to a trampoline whose number differs by at most $A\_i$, that is, to trampoline $j$ with $|i - j| \le A\_i$. For safety, every trampoline can reach trampoline $0$ in one jump, so $A\_i \ge i$ holds.

Minsol, a fan of Mindol, went to Mindol Park and decided to try a Mindol tour, named after the Hamiltonian tour. A Mindol tour starts at trampoline $0$, visits each of the other $N$ trampolines exactly once, and returns to trampoline $0$. Tours with a different visiting order are different tours, so a tour and its reverse are counted separately.

Minsol wants to make every possible Mindol tour once before going home. Count how many times she rides.

The first line contains the number of trampolines other than trampoline $0$, $N$ ($1 \le N \le 200\,000$).

The second line contains $A\_1, A\_2, \dots, A\_N$ ($i \le A\_i \le N$), separated by spaces.

Print the number of possible Mindol tours modulo $10^9+7$ on the first line.

For $N = 3$ and $A = (1, 3, 3)$ the possible tours are $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0$, $0 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 0$, $0 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 0$, and $0 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0$.