最大组合数和问题

题目描述

众所周知，小葱同学擅长计算，尤其擅长计算组合数。现在小葱给了你两个数 $n$ 和 $k$，希望你找到 $k$ 个不同的组合数，使得这 $k$ 个组合数的和最大。

不同组合数的定义

对于组合数 $C_{a_1}^{b_1}$ 和 $C_{a_2}^{b_2}$，若 $a_1 \neq a_2$ 或者 $b_1 \neq b_2$，则认为这两个组合数是不同的。

约束条件

所选的每个组合数 $C_a^b$ 必须满足 $0 \leq b \leq a \leq n$。

请你找出满足条件的 $k$ 个不同组合数，计算它们的最大可能和。

输入格式

从标准输入读入数据：

• 第一行包含两个整数 $n$ 和 $k$，分别表示组合数的上界和需要选择的组合数个数。

输出格式

输出到标准输出：

• 一行一个整数，代表 $k$ 个组合数的和对 $10^9 + 7$ 取模后的结果。
• 数据保证存在至少 $k$ 个符合条件的组合数可供选择。

样例

样例输入

2 3

样例输出

4

样例解释

当 $n=2$ 时，所有符合条件的组合数为：

• $C_0^0 = 1$
• $C_1^0 = 1$、$C_1^1 = 1$
• $C_2^0 = 1$、$C_2^1 = 2$、$C_2^2 = 1$

选择最大的 3 个不同组合数（$C_2^1=2$、$C_0^0=1$、$C_1^0=1$，或其他任意 3 个和为 4 的组合），其和为 4。

数据范围与提示