配点: 7 点
問題文
长度 小于或等于 N 的正整数序列 给出了 A = (A_1,A_2,A_3,\cdots, A_N) 。 对于
将此数列 1 个以上的非空连续区间分割的方法是 2^{N-1} 有几条路,但请计算满足以下条件的数量。
- 对于所有区间,在该区间内 冒泡排序的交换次数 是 在 K 下面。
但是,由于答案可能非常大,10^9+7 后的余数。
冒泡排序的交换次数是指
「"A_i > A_{i+1} 如果成立,将那两个数进行交换的操作 i = 1, 2, \cdots, N-1 按顺序进行"称为 1 次扫描。因此,通过重复扫描 N-1 次,可知可以将数列按升序排序。在这里,定义在应用该算法时进行整数交换的次数为冒泡排序的交换次数。
例如 第 A = (2, 4, 3, 1) 的情况下,冒泡排序的交换次数是 4 。
制約
- 1\leq N\leq 2 \times 10^5
- 0\leq K\leq \frac{N(N-1)}2
- 1\leq A_i\leq 10^9
- 所有输入均为整数
小課題
- (1 点): K=0
- (1 点): N\leq 15
- (1 点): N\leq 800
- (2 点): N\leq 10000
- (2 分数):没有额外约束。
入力
输入以以下形式给出。
N K A_1 A_2 A_3 \cdots A_N
出力
满足题目中条件的分割方法的数量 10^9+7 后的余数 1 行输出。
入力例 1
4 0 3 1 4 2
出力例 1
2
\{3\}, \{1,4\}, \{2\} 这样的分割和,\{3\}, \{1\}, \{4\}, \{2\} 到 2 Street 满足条件。
入力例 2
7 2 5 3 7 2 1 2 3
出力例 2
44
入力例 3
7 0 7 6 5 4 3 2 1
出力例 3
1