来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 18 套，第 1 题。原题标号：A；原本地编号：Z4P1-18-A。

A 魔法数列的奇妙探索 (magic)

题目描述

在神秘的魔法大陆上，魔法师艾丽发现一本古籍，记载着独特数列魔法。

给定正整数 $N$ 与 $K$，有一序列 $A=(A_0, A_1, \ldots, A_N)$。当 $0\leq i < K$，$A_i = 1$，好似基础魔法符文闪耀。而当 $K\leq i$，$A_i = A_{i - K} + A_{i - K + 1} + \ldots + A_{i - 1}$，如同汇聚前 $K$ 项魔力的魔法绽放。

艾丽好奇 $A_N$ 对 $10^9$ 取模的魔力值。$N$、$K$ 可达 $10^6$，直接计算如陷魔法迷雾。她凭借智慧，探寻规律，运用算法魔法（递推与模运算优化），冲破迷雾。最终，当算出结果，似解古老魔法谜题，数列奥秘如魔法光芒闪耀，成为她魔法求知路上的璀璨印记。

输入格式

• 第一行两个整数 $n$、$k$（$1 \leq k \leq n \leq 10^6$）

输出格式

输出一个整数，表示 $A_N$

样例

样例输入 1

24 7

样例输出 1

755749

样例输入 2

1926081 791981

样例输出 2

205555201

数据范围与约定

测试点编号	性质
$1\sim 3$	$n \leq 10$
$4 \sim 5$	$1 \leq n, k \leq 2 \times 10^3$
$6 \sim 10$	$1 \leq n, k \leq 10^6$

对于 $100\%$ 的数据，满足：

• $1 \leq n, k \leq 10^6$