分数: 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