問題文
新员工高桥作为某公司的新程序员被分配到某个部门。 高桥先生的首要任务是加速下面伪代码所示的程序。
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