C - K-bonacci 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

正整数 N,K が与えられます。長さ N+1 の数列 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}

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 で割ったあまりを出力することに注意してください。

Score : 300 points

Problem Statement

You are given positive integers N and K. Define a sequence A = (A_0, A_1, \ldots, A_N) of length N+1 as follows:

  • A_i = 1 for 0 \le i < K;
  • A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} for K \le i.

Find A_N modulo 10^9.

Constraints

  • 1 \le N, K \le 10^{6}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K

Output

Print the answer.

Sample Input 1

4 2

Sample Output 1

5

We have A_0 = A_1 = 1, and A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5.

Sample Input 2

10 20

Sample Output 2

1

Sample Input 3

1000000 500000

Sample Output 3

420890625

Remember to print A_N modulo 10^9.