|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.
|-||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.|