Description

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?

Input Format

Read from standard input.

The first line contains two integers $n,k$.

Output Format

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.

2 3

4

Hint

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