#6353. 「CodePlus 2018 4 月赛」组合数问题 2

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

题目描述

众所周知,小葱同学擅长计算,尤其擅长计算组合数,所以小葱给了你两个数 nnkk,希望你找到 kk 个不同的组合数使得这 kk 个组合数的和最大。所谓不同的组合数,即对于组合数 Ca1b1C_{a_1}^{b_1}Ca2b2C_{a_2}^{b_2},若 a1a2a_1\neq a_2 或者 b1b2b_1\neq b_2,则我们认为这两个组合数是不同的。现在小葱希望你找到这样 kk 个不同的组合数,使得它们互不相同且对于其中任何一个组合数 CabC_a^b0ban0\leq b\leq a\leq n。问这 kk 个组合数的和最大是多少?

输入格式

从标准输入读入数据。

第一行两个整数 n,kn,k

输出格式

输出到标准输出。

一行一个整数,代表 kk 个组合数的和对 109+710^9+7 取模之后的结果;数据保证一定有至少 kk 个数可以选。

样例

样例输入

2 3

样例输出

4

数据范围与提示

对于 20%20\% 的数据,n10n\leq 10

对于 40%40\% 的数据,n500n\leq 500

对于另外 20%20\% 的数据,k=1k=1

对于 100%100\% 的数据, 1n106,1k1051\leq n\leq 10^6,1\leq k\leq 10^5


来自 CodePlus 第 4 次月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea 与命题/钟皓曦 验题/王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。