電電有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\)取模。

範例輸入 1

5 3
1 4 3 2 5

範例輸出 1

2

範例輸入 2

6 1
4 1 2 3 4 5

範例輸出 2

0

範例輸入 3

7 2
6 6 6 6 6 6 6

範例輸出 3

5

提示

範例1有兩種跳法： 1->2->3->5, 1->2->4->5

範例2不可能只跳一次就跳到，所以答案是0。

範例3：1 -> (2,3,4,5,6) -> 7