### Problem Statement

Rabbit Hanako likes apples. She decided to plant apple trees along a straight road.

The road has D candidate positions for planting apple trees. These positions are numbered 0 through D-1, from left to right. The distance between position x and position y is |x-y| meters (|x-y| denotes the absolute value of x-y). She wants to plant N apple trees numbered from 0 to N-1 in different positions. The trees may be planted in any order. The i-th tree won't grow if there are other trees which are closer than r[i] meters. In other words, if i and j are distinct, the distance between the i-th tree and the j-th tree must be at least max(r[i],r[j]) meters.

Return the number of ways to plant all apple trees modulo 1,000,000,007.

### Definition

 Class: AppleTrees Method: theCount Parameters: int, int[] Returns: int Method signature: int theCount(int D, int[] r) (be sure your method is public)

### Constraints

-D will be between 1 and 100,000, inclusive.
-r will contain between 1 and 40 elements, inclusive.
-Each element of r will be between 1 and 40, inclusive.

### Examples

0)

 `10` `{40}`
`Returns: 10`
 There are 10 candidate positions for the only tree.
1)

 `4` `{1, 1, 1, 1}`
`Returns: 24`
 Trees must be planted in different positions, so the number of ways to plant all trees is 4! = 24.
2)

 `4` `{1, 1, 2}`
`Returns: 4`
 The following 4 ways are possible: Plant the 0th tree in position 0, the 1st tree in position 1, and the 2nd tree in position 3. Plant the 0th tree in position 1, the 1st tree in position 0, and the 2nd tree in position 3. Plant the 0th tree in position 2, the 1st tree in position 3, and the 2nd tree in position 0. Plant the 0th tree in position 3, the 1st tree in position 2, and the 2nd tree in position 0.
3)

 `58` `{5, 8}`
`Returns: 2550`
4)

 `47` `{4, 8, 9}`
`Returns: 28830`
5)

 `100000` `{21, 37, 23, 13, 32, 22, 9, 39}`
`Returns: 923016564`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11213

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14242&pm=11213

rng_58

#### Testers:

liympanda , eleusive , ivan_metelsky , vexorian

#### Problem categories:

Dynamic Programming, Math