電電有N個彈簧床，有一天他覺得很無聊，於是就把他們排成一排，然後從第一個彈簧床開始跳到最後一個彈簧床。
可是他覺得這樣還是很無聊，所以他決定不要一個一個跳，而是一次跳過很多個彈簧床。
對於每個彈簧床i都有一個強度值 $s_i$ ，代表從彈簧床i起跳最多可以跳到彈簧床 $i+s_i$ 。
電電跳了幾次之後還是覺得有點無聊，所以他限制自己跳的次數必須要剛好是 $K$ 。
結合運動、臨場反應跟心算的遊戲果然讓電電玩的很開心，不過他之後開始想....依照他訂的遊戲規則，他總共有幾種完成的方法？
這個答案可能很大，所以請輸出答案除以 $1000000009$ 的餘數。
注意電電在跳彈簧床的時候只能往前跳，不能往後或是原地跳。而且電電必須剛好落在第 $N$ 個彈簧床才算結束，不能跳超過。
第一行是兩個數字$N,K(1 \leq K < N \leq 2000)$。
第二行有 $N$ 個正整數，表示$s_{i}(1 \leq s_i \leq N)$。
輸出電電完成遊戲有幾種方法，並對$1000000009$取模。
5 3 1 4 3 2 5
2
6 1 4 1 2 3 4 5
0
7 2 6 6 6 6 6 6 6
5
範例1有兩種跳法： 1->2->3->5, 1->2->4->5
範例2不可能只跳一次就跳到，所以答案是0。
範例3：1 -> (2,3,4,5,6) -> 7