分数: 300 点
问题陈述
给你正整数 N 和 K。定义一个序列 A = (A_0, A_1, \ldots, A_N) 长度 N+1 如下:
- A_i = 1 为 0 \le i < K;
- A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} 为 K \le i.
查找 A_N 模数 10^9.
约束
- 1 \le N, K \le 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.