AT_abc021_d.[ABC021D] 多重ループ

新入职的高桥君作为某企业的新晋程序员被分配到了部门。他负责的第一项工作是对以下伪代码所表示的程序进行加速。

n←(标准输入)
ans←0
for i=1..n
  for j=i..n
    ans ← ans+1
显示 ans 的值

对于高桥君来说，这样的工作简直是小菜一碟。只要考虑每个 $i$ 的内层循环次数，并利用求和公式，就能得到 $ans=n+n-1+\dots+1=n(n+1)/2$，用这个公式就能立刻算出答案。

高桥君成功实现了显著的加速，部门对他的期待也随之水涨船高。于是上司又给了他更进一步的任务。

这次的任务是：当 for 循环嵌套深度为 $k$ 时，对如下程序进行加速。

n←(标准输入)
k←(标准输入)
ans←0
for a_1=1..n
  for a_2=a_1..n
    for a_3=a_2..n
      …
      for a_k=a_{k-1}..n // 设 a_0=1
        ans ← ans+1
显示 ans 的值

即使是高桥君，这次也有些犯难了，因为无法直接使用求和公式。

经过一番思考，他发现，这个程序输出的答案等于满足 $1\leq a_1\leq a_2\leq\dots\leq a_k\leq n$ 的整数组 $(a_1,a_2,\dots,a_k)$ 的个数。然而，他没能想到如何计算这样的组合数。

作为他的同事，你决定帮他写出解决这个问题的程序。不过，由于答案可能非常大，请输出 $ans$ 对 $1,000,000,007(=10^9+7)$ 取模后的结果。

输入从标准输入按以下格式给出。

$n$ $k$

• 第 $1$ 行给出整数 $n\ (1\leq n\leq 10^5)$。
• 第 $2$ 行给出整数 $k\ (1\leq k\leq 10^5)$。

请输出第 $2$ 个程序最终 $ans$ 的值对 $1,000,000,007$ 取模后的结果。

注意不要忘记输出末尾的换行符。

部分分

本题设有部分分。

• 对于 $1\leq n\leq 1000$ 且 $1\leq k\leq 1000$ 的数据集，答对可得 $99$ 分。
• 对于包含上述数据集在内的所有数据集都答对，可再得 $1$ 分。

由 ChatGPT 4.1 翻译