まえがき
↓の問題が話題に上がって，これBなの！？と思ったやつ．
Kが一般になるとABC-CかABC-Dぐらいの難易度な気がする．
問題
K-ナッチ数列は
a_1 = a_2 = .. = a_{K-1} = 0
a_k = 1
a_i = a_{i-K} + a_{i-K+1} + .. a_{i-1} (i > K)
で定められる．K，Nが与えられるので，a_Nを求めよ．ただし，a_Nは非常に大きくなる可能性があるので，10007で割ったあまりを出力すること．
制約
2sec, 1 <= K, N <= 10^6
方針
i番目の項について愚直に求めるとそれ以前のK項を合計する必要があり，それをN回繰り返すのでO(NK)となり間に合わない．
ここで，K-ナッチ数列の隣接する項を考えると，
a_i = a_{i-K} + a_{i-K+1} + .. a_{i-1}
a_{i+1} = a_{i-K+1} + .. a_{i-1} + a_{i}
と，計算の大部分がほとんど同じであることがわかる．であればK項を毎回合計せずとも，変化する部分のみを差分計算してあげることによってO(N)でもとまりそうです．
注意: O(N+K)ではなくO(N)なのは a_1 + a_2 + ... + a_k = 1なのではじめのK項の総和を求めておく必要がないため．
実装
はじめに挙げた問題に提出してるのでK=3で固定だけど，一般のKにたいしても十分高速で計算ができるはず．
コードテストで速度チェックやってみたけど十分高速．答えがあってるかわからないけど多分あってるでしょう．
