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