问题描述

给定两个正整数 $N$ 和 $K$，定义一个长度为 $N + 1$ 的序列 $A = (A_0, A_1, \dots, A_N)$，规则如下：

• 当 $0 \leq i < K$ 时，$A_i = 1$；
• 当 $K \leq i$ 时，$A_i = A_{i-K} + A_{i-K+1} + \dots + A_{i-1}$。

求 $A_N$ 对 $10^9$ 取模的结果。

约束条件

$1 \leq N, K \leq 10^6$

所有输入值均为整数。

输入

输入从标准输入以以下格式给出：

$N$
$K$

输出

输出答案。

样例输入 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

样例输入 3

1000000 500000

样例输出 3

420890625

注意：输出 $A_N$ 对 $10^9$ 取模的结果。