Hay Pile Reordering

Bessie the cow is causing trouble again in Farmer John's barn. Farmer John has \(N\) hay piles; for each \(i\) with \(1 \le i \le N\), the \(i\)-th pile contains \(h_i\) hay bales. Bessie does not want any of the hay to fall over, so her only allowed operation is the following:

If two adjacent piles have heights that differ by exactly \(1\), she can move the top hay bale from the taller pile to the top of the shorter pile. In other words, if two adjacent piles have heights \(k\) and \(k+1\) (in either order), she can swap one hay bale from the taller pile to the shorter one, effectively interchanging their heights.

After performing a finite number of such operations, how many different height sequences can be obtained (modulo \(10^9+7\))? Two height sequences are considered the same if every corresponding pile has the same number of hay bales.

Note: An important invariant is that if two piles have heights differing by at least \(2\), their relative order (with respect to their positions in the sequence) remains unchanged in all reachable states. As a result, the only flexibility is in reordering adjacent hay piles whose heights are consecutive integers.

This problem can be solved by first partitioning the sequence into maximal contiguous blocks where every adjacent pair satisfies \(|h_i-h_{i+1}|=1\). For a block of length \(m\) (with \(m\ge 2\); a block of length 1 has only one possibility), the number of valid reordering is determined by the fact that while the two numbers which differ by \(1\) can be swapped arbitrarily, the invariant forces the order between any two numbers whose difference is \(\ge2\) to remain as in the original sequence. It turns out that the number of valid orders for a block of length \(m\) is given by the recurrence:

[ f(1)=1, \quad f(2)=2, \quad f(m)=f(m-1)+f(m-2) \quad\text{for}; m\ge3. ]

The final answer is the product of the numbers of valid orders for each block, taken modulo \(10^9+7\).

inputFormat

The first line contains an integer \(N\) \((1 \le N \le 5000)\).

The second line contains \(N\) space-separated integers \(h_1, h_2, \ldots, h_N\) \((1 \le h_i \le 10^9)\).

outputFormat

Output a single integer denoting the number of different height sequences that can be obtained after a finite number of operations, modulo \(10^9+7\).

sample

2
1 2

2