← 返回题目列表

AtCoder · tdpc_semiexp

F. 准急

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

问题陈述

某条线路从车站 1 到车站 N 最多 N 共有几个车站。须根君决定在这条线路上运行准急列车。
  • 准急列车会停靠车站 1,停靠{车站 2, ..., 车站 N-1}的子集,并停靠车站 N 。
  • 连续的 K如果停靠车站数达到或超过某个数,乘客会感到厌烦,所以不会那样做。
求准急列车停靠车站组合的方案数,用 mod 1,000,000,007 表示。

约束

  • 2 ≤ K ≤ N ≤ 1000000

输入格式

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

输出格式

请将答案输出在一行内。

示例输入 1

10 2

示例输出 1

21

示例输入 2

10 10

示例输出 2

255