← 返回题目列表

AtCoder · tdpc_fibonacci

T. 菲博纳奇

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

问题陈述

数列 {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 求出。

约束

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

输入格式

输入是按以下格式从标准输入给出的。
K N

输出格式

将答案输出在一行。

示例输入 1

2 10

示例输出 1

55
K 当等于 2 时,数列为 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...。

示例输入 2

3 10

示例输出 2

105