← 返回题目列表

AtCoder · abc401_c

E. K-博纳奇

中文机器翻译题面 查看原题

分数: 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.