Div 1 600 - RabbitIncreasing

SRM

問題

1 年目 7 月に 1 つがいのウサギが生まれた．それ以降毎年 3 月の時点で満 1 才以上のウサギ 1 つがいは子ウサギ 1 つがいを生む．leaving[i] 年の 11 月には，居るウサギの約半数．具体的には x つがいに対して x が偶数なら x/2 つがい，奇数なら (x+1)/2 つがいのウサギが去っていく．このとき，年功序列で去っていく．
k 年目の 12 月時点で残っているウサギは何つがいか？ mod 1,000,000,009 で答えよ．