K ボナッチ数列 C++編（paizaランク A 相当）

このページにある問題は、はじめに挑戦した「K ボナッチ数列」と同じ問題です。
ここまでの問題で身につけてきた知識や考え方を活用して、再挑戦してみましょう。

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

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

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

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