题目描述

二维平面上有 $n$ 个点 $(x_i,y_i)$，现在这些点中取若干点构成一个集合 $S$，对它们按照 $x$ 坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为 $f(S)$。如下图中，$1\to 2,2\to 3,3\to 5,5\to 6$（数字为下图中从左到右的点编号），将折线分为了 $4$ 部分，每部分连续上升、下降。

现给定 $k$，求满足 $f(S)=k$ 的 $S$ 集合个数。

输入格式

第一行两个整数 $n$ 和 $k$，以下 $n$ 行每行两个数 $(xi,yi)$ 表示第 $i$ 个点的坐标。所有点的坐标值都在 $[1,100000]$ 内，且不存在两个点，$x$ 坐标值相等或 $y$ 坐标值相等。

输出格式

输出满足要求的方案总数$\mod 100007$ 的结果。

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

19

数据规模与约定

对于 $100\%$ 的数据，$n\le 50000,0<k\le 10$