### Problem Statement

Rabbits often feel lonely, even though they breed a lot.

A male rabbit and a female rabbit were born in July (the 7th month) of year 1, in a certain country. They were the only rabbits in the entire country, so they became a couple.

In March (the 3rd month) of every year, each couple who is strictly more than 1 year old will breed one male and one female rabbit. That is, couples born in year y will start breeding in the year y + 2.

Then, in April (the 4th month) of every year, all newly born rabbits will form couples among themselves. Each rabbit will be a member of exactly one couple, and each couple will contain one male and one female rabbit.

You are given a int[] leaving. Each element of leaving is a year in which half of all couples will leave the country in November (the 11th month). If there are an odd number of couples, n, then (n + 1) / 2 couples will leave. Older couples always have priority when leaving. This means that every couple who leaves will have an age greater than or equal to every couple who stays.

How many couples are in this country in December (the 12th month) of year k? Return the answer modulo 1,000,000,009.

### Definition

 Class: RabbitIncreasing Method: getNumber Parameters: int[], int Returns: int Method signature: int getNumber(int[] leaving, int k) (be sure your method is public)

### Constraints

-leaving will contain between 1 and 50 elements, inclusive.
-k will be between 1 and 10,000,000, inclusive.
-Each element of leaving will be between 1 and k, inclusive.
-Elements of leaving will be sorted in strictly increasing order.

### Examples

0)

 `{ 3 }` `3`
`Returns: 1`
 The first couple will breed a pair of rabbits in March of year 3. Since there are 2 couples in November, 1 old pair will leave.
1)

 `{ 5, 9 }` `10`
`Returns: 6`
 In November of year 5, 3 out of 5 couples will leave. In November of year 9, 5 out of 10 couples will leave.
2)

 `{ 5, 10, 15 }` `19`
`Returns: 212`
3)

 `{ 2 }` `10000000`
`Returns: 0`
4)

 ```{ 195, 211, 227, 230, 260, 297, 346, 350, 403, 411, 428, 485, 594, 606, 876 } ``` `1000`
`Returns: 975206486`
 There are a lot of rabbits. Be sure to return the answer modulo 1,000,000,009.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14156&pm=10879

lyrically

#### Testers:

PabloGilberto , ivan_metelsky , keshav_57

Math