文件读写

• 输入文件duty.in
• 输出文件duty.out

限制

• 1000ms
• 512MB

题目描述

程老师是全校出了名的细心，什么事都要提前规划好。开学第一天，他就坐在办公室里，对着一张空白表格发愁——这张表格上要写下这个学期全班的值日安排。

一个学期一共 $n$ 天，程老师需要从中挑选出 $k$ 天来安排值日。就在他准备动笔的时候，校医室发来了一条硬性规定：

任意两个值日不能安排在相邻的两天。换句话说，如果第 $d$ 天安排了值日，那么第 $d+1$ 天必须休息，不能连续两天都值日。

程老师皱了皱眉——这条规定打乱了他原本的计划。本来可以随便挑 $k$ 天的，现在却必须保证选出来的两天之间至少隔着一个休息日。他试着在草稿纸上列了几个方案，发现当 $n$ 和 $k$ 变大时，手动枚举根本列不完。

请你帮程老师算一算：在满足校医室规定的前提下，挑选 $k$ 天值日的方案一共有多少种？

答案可能很大，输出它对 $10^9 + 7$ 取模的结果。

如果 $k = 0$，即一天值日都不安排，方案数为 $1$。

输入格式

一行两个整数 $n, k$，用一个空格隔开。

输出格式

一行一个整数，表示合法方案数对 $10^9 + 7$ 取模的结果。

数据范围

对于 $100\%$ 的数据，保证 $1 \leq n \leq 2000$，$0 \leq k \leq n$。

5 2

6

3 1

3

4 3

0

样例解释

样例1：$n = 5$，$k = 2$。所有合法选法为 $\{1, 3\}$、$\{1, 4\}$、$\{1, 5\}$、$\{2, 4\}$、$\{2, 5\}$、$\{3, 5\}$，共 $6$ 种方案。