D - Arrangement of Trees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、まっすぐな道に沿って一列に並んだ N 個の区画に植木を植える計画を立てています。区画は左から順に区画 1 , 区画 2 , \ldots , 区画 N と番号が付けられています。

高橋君はこれらの N 個の区画からちょうど K 個の区画を選び、選んだ各区画に植木を 1 本ずつ植えます（選ばなかった区画には植木を植えません）。ただし、植木の間隔を確保するため、以下のルールに従わなければなりません。

  • 隣り合う 2 つの区画をどちらも選んではならない。すなわち、すべての 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 が、スペース区切りで 1 行で与えられる。

出力

ルールを満たす区画の選び方の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi is planning to plant trees in N plots arranged in a row along a straight road. The plots are numbered from left to right as plot 1, plot 2, \ldots, plot N.

Takahashi will choose exactly K plots from these N plots and plant one tree in each chosen plot (no trees are planted in unchosen plots). However, to ensure adequate spacing between trees, the following rule must be followed:

  • No two adjacent plots may both be chosen. That is, for all i (1 \leq i \leq N - 1), plot i and plot i + 1 must not both be chosen.

How many ways are there to choose the plots while satisfying the rule? Two ways are considered different if the sets of chosen plots are different. Find the answer modulo 10^9 + 7. If there is no valid way to choose the plots, the answer is 0.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • N, K are integers

Input

N K

An integer N representing the number of plots and an integer K representing the number of plots in which to plant trees are given on a single line, separated by a space.

Output

Print on a single line the total number of ways to choose the plots satisfying the rule, modulo 10^9 + 7.

Sample Input 1

5 2

Sample Output 1

6

Sample Input 2

4 3

Sample Output 2

0

Sample Input 3

100 30

Sample Output 3

228350971

Sample Input 4

1000000 400000

Sample Output 4

440859224

Sample Input 5

1 1

Sample Output 5

1