「K ボナッチ数列」を解くために:part3 C編（paizaランク B 相当）

引き続き「K ボナッチ数列」を考えます。
1, 2, ..., K 項目を 1 とし、 K + 1 項目以降は前項 K 項の和となる数列のことを、「K ボナッチ数列」と呼ぶことにします。
K ボナッチ数列の i 項目を KB_i とします。
この K ボナッチ数列の i 項目までの累積和 C_i は C_i = KB_1 + KB_2 + ... + KB_i と定義されます。
整数 K と N が与えられるので、 この K ボナッチ数列の N 項目までの累積和 C_N を 10000 で割ったあまりを求めてください。
今回の問題では N, K の値が小さいことが保証されるため、各項を求めるときに毎回前項 K 項の和を計算しても実行時間制限に間に合います。