#2834. 「JOISC 2018 Day 2」修行

内存限制:256 MiB 时间限制:600 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOISC 2018 Day2 T1「修行 / Asceticism

一天,JOI 君得到了一台时间机器。他决定回到九世纪的日本。他遇见了当时日本最伟大的僧人之一——空海法师。这位法师想要创造一种新的修行方式。

他的修行方式如下:

  • 空海法师要读一本有 N 句话的佛经,这些句子是有顺序的,他必须要按顺序读;
  • 每句话都标有一个从 1 N 的正整数,没有两个不同的句子标有相同数字;
  • 一天被平均分为 N 个时段,他只能在某一天的第 i 个时段读编号为 i 的句子。保证他能在第 i 个时段读完编号为 i 的句子。

空海法师想要尽快读完整部佛经。然而,读完佛经花费的天数取决于佛经有多少句话。空海法师让 JOI 君计算一下,如果他采用最佳方案,用恰好 K 天读完佛经的方案数是多少。

任务

给出文章中句子数 N 和天数 K ,计算空海法师用恰好 K 天读完佛经的方案数,对 10^9+7 取模。

输入格式

从标准输入读入下列数据:

  • 第一行包含两个正整数 N K ,用一个空格隔开。

输出格式

输出空海法师用恰好 K 天读完佛经的方案数,对 10^9+7 取模。

样例

样例输入 1

3 2

样例输出 1

4

样例说明

4 种可能的编号方式:

  • 第一个句子编号为 1 ,下一个句子编号为 3 ,最后一个句子编号为 2 。他在第一天读前两句话(编号分别为 1,3 ),在第二天读最后一句话(编号为 2 )。
  • 三个句子分别编号为 2,1,3
  • 三个句子分别编号为 2,3,1
  • 三个句子分别编号为 3,1,2

样例输入 2

10 5

样例输出 2

1310354

数据范围与提示

所有数据满足 1\le N\le 10^5,1\le K\le N

详细子任务的附加限制及分数如下:

Subtask # 附加限制 分数
1 N\le 10 4
2 N\le 300 20
3 N\le 3\times 10^3 25
4 无附加限制 51