P4370 [Code+#4] Binomial Coefficient Problem 2

It is well known that Xiaocong is skilled at calculation, especially at computing binomial coefficients. Given two numbers $n$ and $k$, he wants you to find $k$ distinct binomial coefficients such that their sum is maximized. By distinct binomial coefficients, for $C_{a_1}^{b_1}$ and $C_{a_2}^{b_2}$, if $a_1\neq a_2$ or $b_1\neq b_2$, we consider them different. Now, please find such $k$ distinct binomial coefficients so that for any one of them $C_a^b$ we have $0\leq b\leq a\leq n$. What is the maximum possible sum of these $k$ binomial coefficients?

Read from standard input. The first line contains two integers $n,k$.

Write to standard output. One line with a single integer, representing the sum of the $k$ binomial coefficients modulo $10^9+7$; it is guaranteed that there are at least $k$ numbers to choose from.

For 20% of the testdata, $n\leq 10$. For 40% of the testdata, $n\leq 500$. For another 20% of the testdata, $k=1$. For 100% of the testdata, $1\leq n\leq 10^6,1\leq k\leq 10^5.$ Credit: https://www.luogu.org/discuss/show/38908 Translated by ChatGPT 5