题目描述

二维平面上有 $n$ 个点 $(x_i, y_i)$，现在从这些点中取若干点构成一个集合 $S$，对它们按照 $x$ 坐标排序，顺次连接，将会构成一些连续上升或下降的折线，设其数量为 $f(S)$。例如，下图中，点的编号为从左到右的顺序：

$$1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 6$$

这条折线被分为了 4 部分，每部分是连续上升或下降的。

现给定一个整数 $k$，要求找出满足 $f(S) = k$ 的集合 $S$ 的数量。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示点的个数和折线段数。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个点的坐标。

所有点的坐标值都在区间 $[1, 10^5]$ 内，且不存在两个点具有相同的 $x$ 坐标或 $y$ 坐标。

输出格式

输出满足要求的方案总数，结果对 $100007$ 取模。

5 1
5 5
3 2
4 4
2 3
1 1

19

数据规模与约定

对于 $100\%$ 的数据，满足 $n \leq 50000$，且 $0 < k \leq 10$。