AT_abc401_c [ABC401C] K-bonacci

You are given positive integers $ N $ and $ K $ . Define a sequence $ A = (A_0, A_1, \ldots, A_N) $ of length $ N+1 $ as follows: - $ A_i = 1 $ for $ 0 \le i < K $ ; - $ A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} $ for $ K \le i $ . Find $ A_N $ modulo $ 10^9 $ .

The input is given from Standard Input in the following format: > $ N $ $ K $

Print the answer.

### Sample Explanation 1 We have $ A_0 = A_1 = 1 $ , and $ A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5 $ . ### Sample Explanation 3 Remember to print $ A_N $ modulo $ 10^9 $ . ### Constraints - $ 1 \le N, K \le 10^{6} $ - All input values are integers.