If you naively compute \(A_i\), it costs a total of \(\mathrm{O}(NK)\), exceeding the execution time limit.

Here, when computing \(A_n\), let us also maintain \(S:=A_{n-K}+\ldots+A_{n-1}\) and update accordingly.

First, initialize \(S=K\). Then, for each \(n=K,K+1,\ldots,N\), do the following:

• Let \(A_n=S\).
• Subtract \(A_{n-K}\) from \(S\).
• Add \(A_n\) to \(S\).

By this procedure, the answer can be found in a total of \(\mathrm{O}(N)\) time. See also the sample code.

Sample code (Python):

n, k = map(int, input().split())
s = k
a = [1 for i in range(n + 1)]
for i in range(k, n + 1):
    a[i] = s
    s -= a[i-k]
    s += a[i]
    s %= 1000000000
print(a[n])