问题描述

给定正整数 $N$ 和 $K$。按以下规则定义长度为 $N+1$ 的数列 $A = (A_0, A_1, \ldots, A_N)$：

• 当 $0 \le i < K$ 时，$A_i = 1$
• 当 $K \le i$ 时，$A_i = A_{i-K} + A_{i-K+1} + \cdots + A_{i-1}$

请计算 $A_N$ 对 $10^9$ 取模后的结果。

输入格式

一行，包含两个整数 $N$ 和 $K$。

输出格式

一个整数，即 $A_N \bmod 10^9$。

样例输入 1

4 2

样例输出 1

5

说明：$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$。

样例输入 2

10 20

样例输出 2

1

说明：$K = 20 > 10$，所以 $A_0 = A_1 = \ldots = A_{10} = 1$。

样例输入 3

1000000 500000

样例输出 3

420890625

评测数据规模

对于所有数据，保证 $1 \le N, K \le 10^6$。