시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB86675.000%

## 문제

Professor JOI is a leading expert on the study of the history of IOI Kingdom. When he was surveying an old temple in IOI Kingdom, he found ruins where the stone pillars were constructed. He also found an old document which was supposedly written by ancient people in IOI Kingdom. The document contains descriptions on the stone pillars. More precisely, the following is written in the document.

• Just after the construction, there were 2N stone pillars, numbered from 1 to 2N.
• Just after the construction, for each k (1 ≤ k ≤ N), there were exactly two stone pillars of height k.
• The earthquake occurred N times. After each earthquake, some of the stone pillars collapsed and their heights decreased by 1. However, other stone pillars were protected by ancient people. These stone pillars did not collapse, and their heights remained the same.
• When an earthquake occurred, for each k (1 ≤ k ≤ N), exactly one stone pillar of height k was protected by ancient people. If there were more than one stone pillar of height k when an earthquake occurred, the stone pillar of height k with largest number was protected. In other words, if the height of the stone pillar i (1 ≤ i ≤ 2N) was hi before an earthquake, then the stone pillar i was protected if and only if hi ≥ 1 and hj ≠ hi for every j > i.
• After the N earthquakes occurred, N stone pillars remained (i.e. there were exactly N stone pillars with height at least 1).

Professor JOI thinks it would be a great discovery if he can recover the heights of the 2N stone pillars when they were constructed. He surveyed the place where the stone pillars were constructed in more detail. He found that, after the N earthquakes occurred, the indices of the remaining stone pillars were A1, A2, . . . , AN.

Professor JOI wants to know the number of possible combinations of the heights of the 2N stone pillars when they were constructed. Since you are a pupil of Professor JOI, you are asked to write a program which counts this number.

Write a program which, given the indices of the remaining stone pillars after the N earthquakes occurred, calculates the number of possible combinations of the heights of the 2N stone pillars when they were constructed, modulo 1 000 000 007.

## 입력

Read the following data from the standard input. All the values in the input are integers.

N
A1 · · · AN

## 출력

Write one line to the standard output. Output the remainder when the answer is divided by 1 000 000 007.

## 제한

• 1 ≤ N ≤ 600.
• 1 ≤ Ai ≤ 2N (1 ≤ i ≤ N).
• Ai < Ai+1 (1 ≤ i ≤ N − 1).

번호 배점 제한
1 6

N ≤ 13.

2 52

N ≤ 60.

3 42

## 예제 입력 1

3
3 4 6


## 예제 출력 1

5


For example, assume that the heights of the stone pillars were (2, 2, 3, 3, 1, 1), from the stone pillar 1. Since there were exactly two stone pillars of height k for each k (1 ≤ k ≤ 3), it agrees with the description in the old document.

• When the first earthquake occurred, the stone pillars 2, 4, 6 were protected by ancient people. After the first earthquake, the heights of the stone pillars became (1, 2, 2, 3, 0, 1).
• When the second earthquake occurred, the stone pillars 3, 4, 6 were protected by ancient people. After the second earthquake, the heights of the stone pillars became (0, 1, 2, 3, 0, 1).
• When the third earthquake occurred, the stone pillars 3, 4, 6 were protected by ancient people. After the third earthquake, the heights of the stone pillars became (0, 0, 2, 3, 0, 1).

After the three earthquakes, the stone pillars 3, 4, 6 remained. It coincides with the information given in the input.

In addition to the above, there are four possible combinations of the heights of the stone pillars (2, 3, 2, 3, 1, 1), (2, 3, 3, 2, 1, 1), (3, 2, 2, 3, 1, 1), (3, 2, 3, 2, 1, 1).

Therefore, there are five possible combinations of the heights of the six stone pillars which agree with the description in the old document and the information given in the input.

## 예제 입력 2

1
1


## 예제 출력 2

0


In this sample input, (1, 1) is the only combination of the heights of the stone pillars which agrees with the description in the old document. After the first earthquake, the heights of the stone pillars became (0, 1).

Therefore, there is no possible combination of the heights of the stone pillars which agrees with the description in the old document and the information given in the input.

## 예제 입력 3

10
5 8 9 13 15 16 17 18 19 20


## 예제 출력 3

147003663


There are 111 147 004 440 possible combinations of the heights of the 2N stone pillars, when they were constructed. When 111 147 004 440 is divided by 1 000 000 007, the remainder is 147 003 663. Thus, output 147 003 663.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.