AT_abc021_d [ABC021D] 多重ループ

[problemUrl]: https://atcoder.jp/contests/abc021/tasks/abc021_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 $ 行目に、$ 2 $ つ目のプログラムにおける最終的な ans の値を $ 1,000,000,007 $ で割った余りを出力してください。 末尾の改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。 - $ 1≦n≦1000 $ かつ $ 1≦k≦1000 $ であるようなデータセットに正解した場合は $ 99 $ 点が得られる。 - 上記のデータセットを含む全てのデータセットに正解した場合はさらに $ 1 $ 点が得られる。