题目描述

星际航天局正在规划一项深空探测任务。航天器需要从基地出发，依次经过 $k+1$ 个不同的目标轨道高度来进行逐级加速。

控制中心已经提前测绘出了航天器沿途将会经过的 $n$ 个空间交会点，并按照它们出现的先后顺序排列。第 $i$ 个交会点所对应的目标轨道高度为一个正整数 $a_i$。由于空间环境复杂，这 $n$ 个交会点的高度互不相同。

为了确保航天器能够安全、平稳地通过引力弹弓效应加速，轨道的规划必须满足“逐级严格上升”的物理原则。也就是说，航天器需要从中挑选出 $k+1$ 个交会点组成一条轨道链，且这条轨道链上的目标轨道高度必须满足严格单调递增。

现在，航天局的工程师想知道，一共有多少种不同的合法轨道链规划方案？

保证最终符合条件的方案总数不超过 $8 \times 10^{18}$。

输入格式

第一行包含两个正整数 $n$ 和 $k$（$1 \leq n \leq 10^{5}$，$0 \leq k \leq 10$），分别表示沿途测绘出的空间交会点总数量，以及合格轨道链中所需要的加速级数（注：总共需要选取 $k+1$ 个交会点）。

接下来 $n$ 行，每行包含一个正整数 $a_{i}$（$1 \leq a_{i} \leq n$），依次表示每个空间交会点对应的目标轨道高度。保证所有 $a_{i}$ 互不相同。

输出格式

输出一个整数，表示满足“逐级严格上升”条件的不同轨道链规划方案总数量。

样例 1

5 2
1
2
3
5
4

7

样例说明

数据范围

• 对于 $30\%$ 的数据，$1 \le n\leq 100$。
• 对于 $100\%$ 的数据，$1 \le n\leq 1 \cdot 10^5$。