AT_abc401_c [ABC401C] K-bonacci

正整数 $ N,K $ が与えられます。長さ $ N+1 $ の数列 $ A=(A_0,A_1,\ldots,A_N) $ の各要素の値を、以下の方法で定義します。 - $ 0\leq i

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $

答えを出力せよ。

### Sample Explanation 1 $ A_0=A_1=1 $ であり、 $ A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5 $ となります。 ### Sample Explanation 3 $ A_N $ を $ 10^9 $ で割ったあまりを出力することに注意してください。 ### Constraints - $ 1\leq N, K\leq 10^{6} $ - 入力される数値は全て整数