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

説明

前の問題で求めた累積和を用いて、K ボナッチ数列の N 項目を高速に求めることを考えます。
前の問題と同様に、K ボナッチ数列の i 項目を KB_i、i 項目までの累積和を C_i とします。
N ≦ K の場合は K ボナッチ数列の定義より KB_N = 1 であるため、以下 N > K の場合を考えます。
i 項目までの累積和 C_i は、C_i = KB_i + C_{i-1} として高速に求めることができます (C_0 = 0 とします)。
K ボナッチ数列の N 項目は N-K 項目 ~ N-1 項目の和、つまり KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-1} です。
累積和は K ボナッチ数列の i 項目までの和であり、 C_i = KB_1 + KB_2 + ... + KB_i でした。
KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-1} を累積和を用いた形に変形することで KB_N を高速に求める方法を考えてみましょう。

問題

整数 K と N が与えられるので、 K ボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。