Time Limit: 2 sec / Memory Limit: 256 MB
問題文
新入社員の高橋君は、とある企業の新人プログラマーとして部署に配属されました。 高橋君が担当した初めての仕事は、以下の擬似コードで表されるプログラムを高速化するというものでした。
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