← 返回题目列表

AtCoder · abc021_d

D. 多个循环

中文机器翻译题面 查看原题

問題文

新员工高桥作为某公司的新程序员被分配到某个部门。 高桥先生的首要任务是加速下面伪代码所示的程序。

n←(標準入力)
ans←0
for i=1..n
  for j=i..n
    ans ← ans+1
ansの値を表示

如果是高桥君的话,这种工作简直就是小事一桩。 每个 如果我们考虑 i 的内循环数量并使用求和公式, ans=n+n-1+…+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≦a_1≦a_2≦…≦a_k≦n 我意识到它等于 (a_1,a_2,…,a_k) 的数量。 但他想不出有什么办法来统计这些东西。

作为他的同事,您决定编写一个程序来为他完成此任务。 然而,答案可能非常大,所以用 ans 代替 ans。 请打印除以 1,000,000,007(=10^9+7) 后的余数。


入力

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

n
k
  • 1 行包含一个整数 如果您对 n (1 ≦ n ≦ 10^5) 。
  • 2 行包含一个整数 如果您对 k (1 ≦ k ≦ 10^5) 。

部分点

针对此问题设置了部分分数。

  • 1≦n≦1000 和 满足 1≦k≦1000 等数据集回答正确 获得 99 点。
  • 如果您对包括上述数据集在内的所有数据集都回答正确,那么 在 1 点。

出力

1 行上,2 第二个程序中ans的最终值为 1,000,000,007 后的余数。

不要忘记最后的换行符。


入力例1

10
2

出力例1

55

入力例2

10
3

出力例2

220

入力例3

10
4

出力例3

715

入力例4

400
296

出力例4

546898535

入力例5

100000
100000

出力例5

939733670