T - フィボナッチ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

数列 {a_i} を次のように定義する。
  • a_1 = a_2 = ... = a_K = 1
  • a_i = a_{i-1} + ... + a_{i-K} (i > K)
a_N を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ K ≤ 1000
  • 1 ≤ N ≤ 10^9

Input Format

入力は以下の形式で標準入力から与えられる。
K N

Output Format

答えを一行に出力せよ。

Sample Input 1

2 10

Sample Output 1

55
K = 2 のとき数列は 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... となる。

Sample Input 2

3 10

Sample Output 2

105