Ancient Stone Pillars Restoration

In the ancient ruins, Professor JOI discovered a row of stone pillars and an ancient document. According to the document, when built, there were exactly 2×N stone pillars. For every integer k (1 ≤ k ≤ N), there were two pillars with height k. Denote the height of the i-th pillar by \(h_i\).

Then, N earthquakes occurred one after another. In each earthquake, some of the pillars lost 1 unit of height while others remained unchanged. In fact, during an earthquake the i-th pillar's height remains unchanged if and only if \(h_i \ge 1\) and for every pillar \(j\) with \(j > i\) it holds that \(h_i \neq h_j\). (In other words, in each earthquake, for each distinct height value among the current heights, only the rightmost occurrence (i.e. the one with the greatest index) is immune.)

After N earthquakes, exactly N pillars remain (their heights remain positive) while the others have dropped to 0. Professor JOI has determined the positions \(A_1,A_2,\dots,A_N\) (1-indexed) of the surviving pillars. Your task is to calculate, modulo \(10^9+7\), the number of possible original building schemes (i.e. assignments of the initial heights \(h_1, h_2, \dots, h_{2N}\)) that would yield the survivors exactly at these positions.

Observation: Since initially there are two pillars of each height from 1 to \(N\) and throughout each earthquake for each height the column with the larger index does not drop, a valid configuration must satisfy that for every height, the surviving pillar (which never loses any height) appears to the right of its partner. It can be shown that the number of valid configurations is given by

[ \prod_{i=1}^{N} (A_i - i) \pmod{10^9+7}. ]

inputFormat

The input consists of two lines.

The first line contains a single integer \(N\) (\(1 \leq N \leq 10^5\)).

The second line contains \(N\) distinct integers \(A_1,A_2,\dots,A_N\) (\(1 \leq A_i \leq 2N\)). These denote the positions (1-indexed) of the surviving pillars after all earthquakes. The \(A_i\) values may be given in any order.

outputFormat

Output a single integer: the number of valid original building schemes modulo \(10^9+7\).

sample

2
2 4

2