K ボナッチ数列 VB(Beta)編（paizaランク A 相当）

これは、A ランクの問題として出題されていた問題です。試しに解いてみましょう。
現時点では自力で正解することができない場合は、この問題を飛ばして次の問題に進んでください。
後に続く 5 つの問題に順番に取り組むことで、この問題を解くために必要な知識や考えた方を身につけることができます。
A ランク獲得に向けた学習にお役立てください。

「フィボナッチ数列」とは、1, 2 項目を 1 とし、 3 項目以降は前項 2 項の和となる数列です。

ここでは、1, 2, ..., K 項目を 1 とし、 K + 1 項目以降は前項 K 項の和となる数列のことを、「K ボナッチ数列」と呼ぶことにします。

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

例えば、入力例 1 の 3 ボナッチ数列の様子は、以下の画像のとおりです。