← 返回题目列表

AtCoder · arc138_e

E. 递减子序列

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

分数: 1000 点

问题陈述

给你整数 N 和 K。 让我们调用一个整数序列 A=(A_1,A_2,\cdots,A_N) 好 当满足以下所有条件时。

  • 0 \leq A_i \leq i (1 \leq i \leq N)
  • 对于每个整数 v=1,2,\cdots,N,最多有一个索引 i 这样 A_i=v.

求总和,模 (10^9+7),所有好的序列的以下问题的答案 A.

  • 求长度-的数量K (不一定连续)的子序列 A 由递减的正整数组成。换句话说,找到索引序列的数量 1 \leq i_1 < i_2 < \cdots < i_K \leq N 这样 A_{i_1}>A_{i_2}>\cdots>A_{i_K} \geq 1.

约束

  • 3 \leq N \leq 5000
  • 2 \leq K
  • 2K-1 \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K

输出

打印答案。


示例输入 1

3 2

示例输出 1

1

例如, A=(0,2,1) 是一个好的序列,有一个子序列满足条件。 还有其他好的序列,例如 A=(0,1,0),(1,2,3),(0,0,0),但它们都没有满足条件的子序列。 最后除了 A=(0,2,1) 有满足条件的子序列,所以答案是 1.


示例输入 2

6 2

示例输出 2

660

示例输入 3

10 3

示例输出 3

242595

示例输入 4

100 10

示例输出 4

495811864