← 返回题目列表

AtCoder · awc0037_d

D. 树木的排列

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

分数: 400 分

问题陈述

高桥正计划在 N 地块沿着笔直的道路排成一排。这些图从左到右编号为图 1,情节 2, \ldots,情节 N.

高桥会准确选择 K 这些图 N 地块并在每个选定的地块中种植一棵树(未选择的地块中不种植树木)。然而,为了确保树之间有足够的间距,必须遵循以下规则:

  • 不能同时选择两个相邻的地块。也就是说,对于所有 i (1 \leq i \leq N - 1),情节 i 和情节 i + 1 不得同时选择。

在满足规则的情况下,有多少种选择地块的方法?如果所选地块的集合不同,则两种方法被认为是不同的。求出模数的答案 10^9 + 7。如果没有有效的方法来选择地块,答案是 0.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • N, K 是整数

输入

N K

一个整数 N 代表绘图数和一个整数 K 表示种植树木的地块数量,在一行中给出,并用空格分隔。

输出

在单行上打印选择满足规则的图的方法总数,模数 10^9 + 7.


样本输入 1

5 2

示例输出 1

6

示例输入 2

4 3

示例输出 2

0

示例输入 3

100 30

示例输出 3

228350971

示例输入 4

1000000 400000

示例输出 4

440859224

示例输入 5

1 1

示例输出 5

1