AtCoder Beginner Contest 021

D - 多重ループ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

新入社員の高橋君は、とある企業の新人プログラマーとして部署に配属されました。 高橋君が担当した初めての仕事は、以下の擬似コードで表されるプログラムを高速化するというものでした。

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

Submit提出する